oj.uz

Submission #814035

# Submission time Handle Problem Language Result Execution time Memory
814035 2023-08-08T05:09:22 Z 반딧불(#10119) Posters on the wall (CPSPC17_posters) C++17
60 / 100
 439 ms 38796 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    ll a[1<<20], b[1<<20], lazyA[1<<20], lazyB[1<<20];

    void propagate(int i, int l, int r){
        a[i] += lazyA[i] * (r-l+1), b[i] += lazyB[i] * (r-l+1);
        if(l!=r) lazyA[i*2] += lazyA[i], lazyA[i*2+1] += lazyA[i], lazyB[i*2] += lazyB[i], lazyB[i*2+1] += lazyB[i];
        lazyA[i] = lazyB[i] = 0;
    }

    void update(int i, int l, int r, int s, int e, ll av, ll bv){
        propagate(i, l, r);
        if(r<s || e<l) return;
        if(s<=l && r<=e){
            lazyA[i] = av, lazyB[i] = bv;
            propagate(i, l, r);
            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);
        a[i] = a[i*2] + a[i*2+1], b[i] = b[i*2] + b[i*2+1];
    }

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

struct Event{
    int type, y, l, r, a, b; /// type: 0 ���簢�� ����, 1 ���簢�� �߰�, 2 ����
    Event(){}
    Event(int type, int y, int l, int r, int a, int 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++){
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &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++){
        int x1, y1, x2, y2, v;
        scanf("%d %d %d %d %d", &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));
    }
    sort(vec.begin(), vec.end());
    const int MX = 300000;
    for(Event &p: vec){
        if(p.type <= 1) tree.update(1, 1, MX, p.l, p.r, p.a, p.b);
        else ans[p.b] += tree.query(1, 1, 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:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 15 ms 1704 KB Output is correct
5 Correct 20 ms 1740 KB Output is correct
6 Correct 15 ms 1684 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 15 ms 1704 KB Output is correct
5 Correct 20 ms 1740 KB Output is correct
6 Correct 15 ms 1684 KB Output is correct
7 Correct 439 ms 37380 KB Output is correct
8 Correct 234 ms 38796 KB Output is correct
9 Correct 199 ms 38592 KB Output is correct
10 Correct 230 ms 38664 KB Output is correct
11 Correct 208 ms 38704 KB Output is correct
12 Correct 208 ms 38720 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 15 ms 1704 KB Output is correct
5 Correct 20 ms 1740 KB Output is correct
6 Correct 15 ms 1684 KB Output is correct
7 Incorrect 101 ms 15704 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 596 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 15 ms 1704 KB Output is correct
5 Correct 20 ms 1740 KB Output is correct
6 Correct 15 ms 1684 KB Output is correct
7 Correct 439 ms 37380 KB Output is correct
8 Correct 234 ms 38796 KB Output is correct
9 Correct 199 ms 38592 KB Output is correct
10 Correct 230 ms 38664 KB Output is correct
11 Correct 208 ms 38704 KB Output is correct
12 Correct 208 ms 38720 KB Output is correct
13 Incorrect 101 ms 15704 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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