답안 #783253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
783253 2023-07-14T18:56:27 Z AmirElarbi 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
331 ms 137216 KB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define INF 1e9
#define ve vector
#define vi ve<int>
#define ii pair<int,int>
#define vii ve<ii>
#define pb push_back
#define fi first
#define se second
using namespace __gnu_pbds;
using namespace std;
const int MOD = 1e9+7;
const int nax = 1e5+5;
const int kax = 25+5;
#include<bits/stdc++.h>
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <class T> struct node
{
    T val = 0; T lazy = 0;  node<T>* c[2];
    node() {c[0] = c[1] = NULL; }
    void push_lazy(int l, int r){
        if(lazy){
            int md = (l+r)/2;
            if(!c[0]) c[0] = new node(); 
            c[0]->val = (md-l+1);
            if(!c[1]) c[1] = new node();
            c[1]->val = (r-md);
            c[0]->lazy = c[1]->lazy = 1;
            lazy = 0; 
        }
    }
    void update(int l, int r, int i, int j){
        if(r < i || l > j) return;
        if(i <= l && r <= j){ val = (r-l+1); lazy = 1; return; }
        push_lazy(l,r);
        int md = (l+r)/2;
        if(i <= md){
            if(!c[0]) c[0] = new node();
            c[0]->update(l,md,i,j);
        } 
        if(j > md){
            if(!c[1]) c[1] = new node();
            c[1]->update(md+1,r,i,j);
        }
        val = 0;
        for(int i = 0; i < 2; i++) if(c[i]) val += c[i]->val;
        //cout << l << ' ' << r << " " << val << endl;
    }
    T query(int l, int r, int i, int j) {
        if(r < i || l > j) return 0;
        if(i <= l && r <= j) return val;
        push_lazy(l,r);
        int md = (l+r)/2; T res = 0;
        if(c[0]) res += c[0]->query(l,md,i,j);
        if(c[1]) res += c[1]->query(md+1,r,i,j);
        return res;
    }
};
 
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int m;
    cin >> m;
    int c = 0;
    node<int> rt = node<int>();
    for (int i = 0; i < m; ++i)
    {
        int d, x, y;
        cin >> d >> x >> y;
        x--,y--;
        if(d == 1){
            int ans = rt.query(0,INF, x+c, y+c);
            cout << ans << endl;
            c = ans;
        } else {
            //cout << x+c << " " << y+c << endl;
            rt.update(0,INF,x+c, y+c);
        }
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 13 ms 3300 KB Output is correct
5 Correct 16 ms 4052 KB Output is correct
6 Correct 16 ms 3840 KB Output is correct
7 Correct 16 ms 3924 KB Output is correct
8 Correct 112 ms 29244 KB Output is correct
9 Correct 215 ms 50512 KB Output is correct
10 Correct 234 ms 56044 KB Output is correct
11 Correct 249 ms 60108 KB Output is correct
12 Correct 236 ms 62024 KB Output is correct
13 Correct 225 ms 72260 KB Output is correct
14 Correct 221 ms 72848 KB Output is correct
15 Correct 319 ms 133196 KB Output is correct
16 Correct 331 ms 134324 KB Output is correct
17 Correct 222 ms 75340 KB Output is correct
18 Correct 219 ms 75428 KB Output is correct
19 Correct 329 ms 137140 KB Output is correct
20 Correct 319 ms 137216 KB Output is correct