답안 #924815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
924815 2024-02-09T18:27:02 Z Karoot 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
178 ms 153900 KB
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}


struct Node {
    ll sum;
    bool lzSet;
    int l, r;
    Node() : sum(0), lzSet(0), l(-1), r(-1) {}
};

const int MAXN = 1e5+1;
Node ST[64*MAXN];
int cnt = 2;

void pushup(int p){
    ST[p].sum = (ST[ST[p].l].sum + ST[ST[p].r].sum);
}

void pushdown(int p, int l, int r){
    int mid = (l+r)/2;
    int a = ST[p].l, b = ST[p].r;
    ST[a].lzSet |= ST[p].lzSet;
    ST[b].lzSet |= ST[p].lzSet;
    ST[a].sum = (ST[a].lzSet ? (mid-l+1) : ST[a].sum);
    ST[b].sum = (ST[b].lzSet ? (r - mid) : ST[b].sum);
    ST[p].lzSet = 0;
    return;
}

void update(int p, int l, int r, int a, int b){
    if (a == l && b == r){
        ST[p].sum = r-l+1;
        ST[p].lzSet = 1;
        return;
    }
    int mid = (l+r)/2;
    if (ST[p].l == -1){
        ST[p].l = cnt++;
        ST[ST[p].l];
    }
    if (ST[p].r == -1){
        ST[p].r = cnt++;
        ST[ST[r].l];
    }
    pushdown(p, l, r);
    
    if (b <= mid){
        update(ST[p].l, l, mid, a, b);
    } else if (a >= mid+1){
        update(ST[p].r, mid+1, r, a, b);
    } else {
        update(ST[p].l, l, mid, a, mid);
        update(ST[p].r, mid+1, r, mid+1, b);
    }
    pushup(p);
    return;
}

ll query(int p, int l, int r, int a, int b) {
	if (a == l && r == b) return ST[p].sum;
	int mid = (l + r) >> 1;
    if (ST[p].l == -1){
        ST[p].l = cnt++;
        ST[ST[p].l];
    }
    if (ST[p].r == -1){
        ST[p].r = cnt++;
        ST[ST[r].l];
    }
	pushdown(p, l, r);
    if (b <= mid){
        return query(ST[p].l, l, mid, a, b);
    }
    if (a >= mid+1){
        return query(ST[p].r, mid+1, r, a, b);
    
    }
	return query(ST[p].l, l, mid, a, mid) + query(ST[p].r, mid + 1, r, mid+1, b);
}



int main(){
    scoobydoobydoo();
    int q; cin >> q;
    vector<ll> ans;
    ST[1];
    ll C = 0;
    while (q--){
        int t, x, y; cin >> t >> x >> y;
        if (t == 2){
            update(1, 0, 1e9, x+C, y+C);
        } else {
            ans.push_back(query(1, 0, 1e9, x+C, y+C));
            C = ans[ans.size()-1];
        }
    }

    for (auto& e : ans){
        cout << e << "\n";
    }


    return 0;
}

Compilation message

apple.cpp: In function 'void update(int, int, int, int, int)':
apple.cpp:63:19: warning: statement has no effect [-Wunused-value]
   63 |         ST[ST[p].l];
      |         ~~~~~~~~~~^
apple.cpp:67:19: warning: statement has no effect [-Wunused-value]
   67 |         ST[ST[r].l];
      |         ~~~~~~~~~~^
apple.cpp: In function 'll query(int, int, int, int, int)':
apple.cpp:88:19: warning: statement has no effect [-Wunused-value]
   88 |         ST[ST[p].l];
      |         ~~~~~~~~~~^
apple.cpp:92:19: warning: statement has no effect [-Wunused-value]
   92 |         ST[ST[r].l];
      |         ~~~~~~~~~~^
apple.cpp: In function 'int main()':
apple.cpp:111:9: warning: statement has no effect [-Wunused-value]
  111 |     ST[1];
      |     ~~~~^
# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 150516 KB Output is correct
2 Correct 29 ms 150612 KB Output is correct
3 Correct 29 ms 150616 KB Output is correct
4 Correct 36 ms 150868 KB Output is correct
5 Correct 38 ms 150904 KB Output is correct
6 Correct 39 ms 151284 KB Output is correct
7 Correct 38 ms 150868 KB Output is correct
8 Correct 82 ms 151968 KB Output is correct
9 Correct 152 ms 153296 KB Output is correct
10 Correct 170 ms 153292 KB Output is correct
11 Correct 155 ms 153328 KB Output is correct
12 Correct 154 ms 153300 KB Output is correct
13 Correct 156 ms 153812 KB Output is correct
14 Correct 148 ms 153808 KB Output is correct
15 Correct 175 ms 153692 KB Output is correct
16 Correct 175 ms 153704 KB Output is correct
17 Correct 145 ms 153776 KB Output is correct
18 Correct 146 ms 153804 KB Output is correct
19 Correct 178 ms 153724 KB Output is correct
20 Correct 177 ms 153900 KB Output is correct