답안 #783249

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
783249 2023-07-14T18:53:51 Z AmirElarbi 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
1 ms 212 KB
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define INF 1e9+5
#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(!c[0]) c[0] = new node();
        c[0]->update(l,md,i,j);
        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 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -