oj.uz

Submission #814426

# Submission time Handle Problem Language Result Execution time Memory
814426 2023-08-08T07:25:36 Z 반딧불(#10119) Posters on the wall (CPSPC17_posters) C++17
80 / 100
 276 ms 35872 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<ll> vx;

struct segTree{
    ll a[1<<20], b[1<<20], aSum[1<<20], bSum[1<<20];

    void update(int i, int l, int r, int s, int e, ll av, ll bv){
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            a[i] += av, b[i] += bv;
            aSum[i] += av * (vx[r+1] - vx[l]), bSum[i] += bv * (vx[r+1] - vx[l]);
            return;
        }
        int m = (l+r)>>1;
        update(i*2, l, m, s, e, av, bv);
        update(i*2+1, m+1, r, s, e, av, bv);
        aSum[i] = aSum[i*2] + aSum[i*2+1] + a[i] * (vx[r+1] - vx[l]);
        bSum[i] = bSum[i*2] + bSum[i*2+1] + b[i] * (vx[r+1] - vx[l]);
    }

    ll query(int i, int l, int r, int s, int e, ll t, ll aup=0, ll bup=0){
        if(r<s || e<l) return 0;
        if(s<=l && r<=e) return (aSum[i] + aup * (vx[r+1] - vx[l])) * t + (bSum[i] + bup * (vx[r+1] - vx[l]));
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e, t, aup + a[i], bup + b[i]) + query(i*2+1, m+1, r, s, e, t, aup + a[i], bup + b[i]);
    }
} tree;

struct Event{
    int type; ll y, l, r, a, b; /// type: 0 ���簢�� ����, 1 ���簢�� �߰�, 2 ����
    Event(){}
    Event(int type, ll y, ll l, ll r, ll a, ll b): type(type), y(y), l(l), r(r), a(a), b(b){}
    bool operator<(const Event &r)const{
        if(y!=r.y) return y<r.y;
        return type<r.type;
    }
};

int n, q, MOD;
vector<Event> vec;
ll ans[50002];

int main(){
    scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
    for(int i=1; i<=n; i++){
        ll x1, y1, x2, y2;
        scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
        if(x1>x2) swap(x1, x2);
        if(y1>y2) swap(y1, y2);
        x1++, y1++;
        /// [x1, x2] [y1, y2] ������ ���ϴ� ������ �Է��� �ٲ�
        vec.push_back(Event(1, y1, x1, x2, 1, -y1+1));
        vec.push_back(Event(0, y2+1, x1, x2, -1, y2));
    }
    for(int i=1; i<=q; i++){
        ll x1, y1, x2, y2, v;
        scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &v);
        if(x1>x2) swap(x1, x2);
        if(y1>y2) swap(y1, y2);
        x1++, y1++;

        vec.push_back(Event(2, y1-1, x1, x2, -1, i));
        vec.push_back(Event(2, y2, x1, x2, 1, i));
    }

    for(Event &p: vec){
        vx.push_back(p.l);
        vx.push_back(p.r+1);
    }
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    for(Event &p: vec){
        p.l = lower_bound(vx.begin(), vx.end(), p.l) - vx.begin();
        p.r = lower_bound(vx.begin(), vx.end(), p.r+1) - vx.begin() - 1;
    }

    sort(vec.begin(), vec.end());
    const int MX = (int)vx.size() - 2;
    for(Event &p: vec){
        if(p.type <= 1) tree.update(1, 0, MX, p.l, p.r, p.a, p.b);
        else ans[p.b] += tree.query(1, 0, MX, p.l, p.r, p.y) * p.a;
    }
    for(int i=1; i<=q; i++) printf("%lld\n", ans[i]);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 15 ms 2752 KB Output is correct
5 Correct 15 ms 2852 KB Output is correct
6 Correct 14 ms 2728 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 15 ms 2752 KB Output is correct
5 Correct 15 ms 2852 KB Output is correct
6 Correct 14 ms 2728 KB Output is correct
7 Correct 144 ms 22792 KB Output is correct
8 Correct 225 ms 34716 KB Output is correct
9 Correct 203 ms 27132 KB Output is correct
10 Correct 237 ms 35384 KB Output is correct
11 Correct 211 ms 35484 KB Output is correct
12 Correct 193 ms 27188 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 15 ms 2752 KB Output is correct
5 Correct 15 ms 2852 KB Output is correct
6 Correct 14 ms 2728 KB Output is correct
7 Correct 192 ms 28524 KB Output is correct
8 Correct 244 ms 34932 KB Output is correct
9 Correct 200 ms 35448 KB Output is correct
10 Correct 257 ms 35548 KB Output is correct
11 Correct 238 ms 35552 KB Output is correct
12 Correct 213 ms 35488 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 15 ms 2752 KB Output is correct
5 Correct 15 ms 2852 KB Output is correct
6 Correct 14 ms 2728 KB Output is correct
7 Correct 144 ms 22792 KB Output is correct
8 Correct 225 ms 34716 KB Output is correct
9 Correct 203 ms 27132 KB Output is correct
10 Correct 237 ms 35384 KB Output is correct
11 Correct 211 ms 35484 KB Output is correct
12 Correct 193 ms 27188 KB Output is correct
13 Correct 192 ms 28524 KB Output is correct
14 Correct 244 ms 34932 KB Output is correct
15 Correct 200 ms 35448 KB Output is correct
16 Correct 257 ms 35548 KB Output is correct
17 Correct 238 ms 35552 KB Output is correct
18 Correct 213 ms 35488 KB Output is correct
19 Correct 215 ms 28836 KB Output is correct
20 Correct 250 ms 35140 KB Output is correct
21 Correct 260 ms 35548 KB Output is correct
22 Correct 266 ms 35872 KB Output is correct
23 Correct 276 ms 35736 KB Output is correct
24 Correct 207 ms 35756 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 25760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 164 ms 25760 KB Output isn't correct
2 Halted 0 ms 0 KB -