User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

25.0% (1/4)

Description

Original Description

有一天,阿克婭和惠惠一起走在路上聊天。

「惠惠阿,妳最近是不是很久沒用爆裂魔法啦~」

「並沒有喔,我每天還是有練習喔,而且經由長期練習,我現在一天要施放 $10^ 5$ 次爆裂魔法都沒有問題喔~」

「真的喔,那,讓我見識一下吧!帶妳去一個好地方。」

阿克婭帶著惠惠到了一座巨大森林面前。這座森林可以視為一個 $[-10^ {18}, 10^ {18}] \times [-10^ {18}, 10^ {18}]$ 的二維平面,每一個格子點(座標 $(x, y)$ 中,$x, y$ 都是整數的點)都種了一棵樹。這座森林的樹有一個特殊功能:存水。每棵樹一開始的存水量都是 $0$ 單位,每棵樹都沒有存水量的上限,也就是說,每棵樹是可以存下無限多單位的水。

惠惠看到前面的森林是施放爆裂魔法的好地方,於是就開始準備念咒語:「比黑色更黑,比黑暗更暗的漆黑,在此寄託吾真紅的金光吧,覺醒之時的到來,荒謬教會的墮落章理,化作無形的扭曲而顯現吧,Ex-plo...」

「等一下啦,惠惠,直接讓妳釋放爆裂魔法太無聊了,為了讓妳有挑戰一點,我準備了一些東西~」

原來,身為水神的阿克婭,準備了很多的水,來挑戰惠惠的爆裂魔法。已知一單位的水需要一單位的爆裂魔法,才能讓水完全消失。

「接下來有一些指令,我們一同來完成。」阿克婭說道,「指令有倒水跟爆裂兩種。倒水指令是:我會在 $(x_1, y_1)$ 到 $(x_2, y_2)$ 這個線段上(包含兩個端點)所有的格子點上面的樹倒下 $w$ 單位的水,線段不是平行於 $x$ 軸,就是平行於 $y$ 軸。爆裂指令是要請妳告訴我,如果妳在 $(x, y)$ 這個格子點上,使用爆裂魔法的話,會需要使用多少單位,才能讓位於 $(x, y)$ 的那棵樹的水完全消失。」

「不能使用爆裂魔法喔,好難過喔......」

「如果妳成功告訴我每次爆裂指令的答案,並且都是正確的話,我就讓妳對這整座森林使用爆裂魔法。」

「可是我不會算數學阿......」

你,身為惠惠的好友,決定挺身而出來幫助她。惠惠會告訴你每次阿克婭的指令,當發生爆裂指令時,請你告訴惠惠正確的答案。

Original Input Format

輸入的第一行包含一個正整數 $N$ ,代表阿克婭的操作的數量。

接下來的 $N$ 行,每行代表一個指令,依序是惠惠和阿克婭要完成的。指令的格式不外乎是下面兩種:

  • $1 \ x_1 \ y_1 \ x_2 \ y_2 \ w$:倒水指令,代表阿克婭會在 $(x_1, y_1)$ 到 $(x_2, y_2)$ 這個線段上所有的格子點上面的樹倒下 $w$ 單位的水。
  • $2 \ x \ y$:爆裂指令,代表阿克婭要求惠惠算出:如果她在 $(x, y)$ 這個格子點上,使用爆裂魔法,會需要使用多少單位,才能讓位於 $(x, y)$ 的那棵樹的水完全消失。

測試資料範圍限制:

  • $1 \leq N \leq 10^ 5$
  • $x_1, y_1, x_2, y_2, w, x, y$ 全部都是整數
  • $-10^ {18} \leq x_1 \le x_2 \leq 10^ {18}$
  • $-10^ {18} \leq y_1 \le y_2 \leq 10^ {18}$
  • $-10^ {18} \leq x, y \leq 10^ {18}$
  • $1 \leq w \leq 10^ 9$
  • $x_1 = y_1, x_2 = y_2$ 這兩個條件中至少一個會成立

Original Output Format

對於每次爆裂指令,請輸出一個數字:如果惠惠在 $(x, y)$ 這個格子點上,使用爆裂魔法,會需要使用多少單位,才能讓位於 $(x, y)$ 的那棵樹的水完全消失。

Original Sample Input

5
2 0 0
1 1 0 1 2 1
2 1 1
1 0 2 2 2 2
2 1 2

Original Sample Output

0
1
3

Original Limits

  • Time Limit: 2 second
  • Memory Limit: 1024 MB

Program To Be Hacked

#include <bits/stdc++.h>
using namespace std;

struct treap {
    long long pos, val, sum;
    int sz, pri;
    treap *lc, *rc;
    treap(long long p, long long v): 
          pos(p), sum(v), val(v), sz(1), pri(rand()), lc(nullptr), rc(nullptr) {}
    void pull() {
        sum = val, sz = 1;
        if (lc) sz += lc->sz, sum += lc->sum;
        if (rc) sz += rc->sz, sum += rc->sum;
    }
};

treap *merge(treap *a, treap *b) {
    if (!a || !b) return a ? a : b;
    if (a->pri > b->pri) return a->rc = merge(a->rc, b), a->pull(), a;
    else return b->lc = merge(a, b->lc), b->pull(), b;
}

void split(treap *t, long long k, treap *&a, treap *&b) {
    if (!t) return a = b = nullptr, void();
    if (t->pos <= k) a = t, split(t->rc, k, a->rc, b), a->pull();
    else b = t, split(t->lc, k, a, b->lc), b->pull();
}

map<long long, int> dx, dy;

int rev(long long x, map<long long, int> &d) {
    if (d.find(x) != d.end()) return d[x];
    int res = (int)d.size();
    return d[x] = res;
}

const int maxn = 1e6 + 5;
treap *tx[maxn], *ty[maxn];

void insert(treap *&t, long long p, long long v) {
    treap *a, *b;
    split(t, p - 1, a, b);
    t = merge(merge(a, new treap(p, v)), b);
}

long long query(treap *t, long long p) {
    treap *a, *b;
    split(t, p, a, b);
    long long res = (a ? a->sum : 0);
    t = merge(a, b);
    return res;
}

int main() {
    int n; scanf("%d", &n);
    long long last = 0;
    for (int i = 0; i < maxn; ++i) {
        tx[i] = nullptr;
        ty[i] = nullptr;
    }
    for (int i = 0; i < n; ++i) {
        int t; scanf("%d", &t);
        if (t == 1) {
            long long xa, ya, xb, yb, w; 
            scanf("%lld%lld%lld%lld%lld", &xa, &ya, &xb, &yb, &w); 
            assert(xa == xb || ya == yb);
            if (xa == xb) {
                long long p = rev(xa, dx);
                insert(tx[p], min(ya, yb) + 0, +w);
                insert(tx[p], max(ya, yb) + 1, -w);
            } else {
                long long p = rev(ya, dy);
                insert(ty[p], min(xa, xb) + 0, +w);
                insert(ty[p], max(xa, xb) + 1, -w);
            }
        } else {
            long long x, y; scanf("%lld%lld", &x, &y);
            last = query(tx[rev(x, dx)], y) + query(ty[rev(y, dy)], x);
            printf("%lld\n", last);
        }
    }
    return 0;
}

Judge Method

請輸出一個測試資料,使得上述的程式碼會不會得到 Accepted

Sample Code

以下程式碼能產生本題合法但一定不會讓你得到 AC 的測試資料。

#include <cstdio>
int main() {
    printf("1\n2 0 0\n");
}

Input Format

Output Format

Sample Input

Sample Output

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 3000 262144 262144 1