oj.uz

답안 #814056

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
814056 2023-08-08T05:15:45 Z 반딧불(#10119) Posters on the wall (CPSPC17_posters) C++17
80 / 100
 330 ms 34544 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<ll> vx;

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] * (vx[r+1] - vx[l]), b[i] += lazyB[i] * (vx[r+1] - vx[l]);
        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; 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:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 18 ms 2644 KB Output is correct
5 Correct 22 ms 2644 KB Output is correct
6 Correct 18 ms 2616 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 18 ms 2644 KB Output is correct
5 Correct 22 ms 2644 KB Output is correct
6 Correct 18 ms 2616 KB Output is correct
7 Correct 285 ms 21836 KB Output is correct
8 Correct 278 ms 34260 KB Output is correct
9 Correct 260 ms 25828 KB Output is correct
10 Correct 309 ms 34140 KB Output is correct
11 Correct 297 ms 34116 KB Output is correct
12 Correct 238 ms 25948 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 18 ms 2644 KB Output is correct
5 Correct 22 ms 2644 KB Output is correct
6 Correct 18 ms 2616 KB Output is correct
7 Correct 262 ms 34272 KB Output is correct
8 Correct 323 ms 34348 KB Output is correct
9 Correct 243 ms 34124 KB Output is correct
10 Correct 309 ms 34352 KB Output is correct
11 Correct 293 ms 34292 KB Output is correct
12 Correct 250 ms 34268 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 18 ms 2644 KB Output is correct
5 Correct 22 ms 2644 KB Output is correct
6 Correct 18 ms 2616 KB Output is correct
7 Correct 285 ms 21836 KB Output is correct
8 Correct 278 ms 34260 KB Output is correct
9 Correct 260 ms 25828 KB Output is correct
10 Correct 309 ms 34140 KB Output is correct
11 Correct 297 ms 34116 KB Output is correct
12 Correct 238 ms 25948 KB Output is correct
13 Correct 262 ms 34272 KB Output is correct
14 Correct 323 ms 34348 KB Output is correct
15 Correct 243 ms 34124 KB Output is correct
16 Correct 309 ms 34352 KB Output is correct
17 Correct 293 ms 34292 KB Output is correct
18 Correct 250 ms 34268 KB Output is correct
19 Correct 288 ms 34524 KB Output is correct
20 Correct 330 ms 34540 KB Output is correct
21 Correct 249 ms 34264 KB Output is correct
22 Correct 305 ms 34448 KB Output is correct
23 Correct 310 ms 34420 KB Output is correct
24 Correct 300 ms 34544 KB Output is correct

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 230 ms 25548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 230 ms 25548 KB Output isn't correct
2 Halted 0 ms 0 KB -