oj.uz

답안 #544186

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
544186 2022-04-01T09:47:27 Z karthikhegde05 원숭이와 사과 나무 (IZhO12_apple) C++17
100 / 100
 525 ms 256724 KB 
#include<bits/stdc++.h>
using namespace std;


#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, 
    rb_tree_tag, tree_order_statistics_node_update>;

#define ook order_of_key
#define fbo find_by_order

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<long long> vll;
#define PI acos(-1.0)
#define EPS 1e-9
#define INF 1000000000
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define pb push_back
#define mkp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define FOR(i, l, r) for(int i=int(l); i<=int(r); i++)
#define ROF(i, l, r) for(int i=int(r); i>=int(l); --i)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9+7;

void print_out(int x){
    cout<<"Case #"<<x<<": ";
}

const int SZ = 1<<30;
template<class T> struct node {
	T val = 0, lazy=0; node<T>* c[2];
	node() { c[0] = c[1] = NULL; }

    void push(int L, int R){
        if(lazy==0)return;
        val = (R-L+1)*lazy;
        if(L!=R){
            if(!c[0])c[0] = new node();
            if(!c[1])c[1] = new node();
            c[0]->lazy = lazy;
            c[1]->lazy = lazy;
        }
        lazy = 0;
    }

	void upd(int lo, int hi, T v, int L = 0, int R = SZ-1) { // add v
        push(L, R);
        if(hi<L || R<lo)return;
		if (lo<=L && R<=hi) { lazy = v; push(L, R); return; }
		int M = (L+R)/2;	

        if(!c[0])c[0] = new node();
        if(!c[1])c[1] = new node();	
        c[0]->upd(lo, hi, v, L, M);
        c[1]->upd(lo, hi, v, M+1, R);

        
		val = 0; FOR(i,0, 1) if (c[i]) val += c[i]->val;
	}
	T query(int lo, int hi, int L = 0, int R = SZ-1) { // query sum of segment
        push(L, R);
		if (hi < L || R < lo) return 0;
		if (lo <= L && R <= hi) return val;
		int M = (L+R)/2; T res = 0;
		if (c[0]!=NULL) res += c[0]->query(lo,hi,L,M);
		if (c[1]!=NULL) res += c[1]->query(lo,hi,M+1,R);
		return res;
	}
	void UPD(int ind, node* c0, node* c1, int L = 0, int R = SZ-1) { // for 2D segtree
		if (L != R) {
			int M = (L+R)/2;
			if (ind <= M) {
				if (!c[0]) c[0] = new node();
				c[0]->UPD(ind,c0?c0->c[0]:NULL,c1?c1->c[0]:NULL,L,M);
			} else {
				if (!c[1]) c[1] = new node();
				c[1]->UPD(ind,c0?c0->c[1]:NULL,c1?c1->c[1]:NULL,M+1,R);
			}
		} 
		val = (c0?c0->val:0)+(c1?c1->val:0);
	}
};



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int m; cin>>m;

    node<int>* seg = new node<int>();
    
    int c = 0;
	FOR(i, 0, m-1){
		int d, x, y;cin>>d>>x>>y;
		if(d==1){
			c = seg->query(x+c-1, y+c-1);
			cout<<c<<"\n";
		}
		else{
			seg->upd(x+c-1, y+c-1, 1);
		}
	}
    
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 14 ms 5720 KB Output is correct
5 Correct 19 ms 6900 KB Output is correct
6 Correct 19 ms 6680 KB Output is correct
7 Correct 18 ms 6860 KB Output is correct
8 Correct 142 ms 49840 KB Output is correct
9 Correct 290 ms 87884 KB Output is correct
10 Correct 301 ms 94712 KB Output is correct
11 Correct 313 ms 102884 KB Output is correct
12 Correct 323 ms 106312 KB Output is correct
13 Correct 304 ms 134324 KB Output is correct
14 Correct 303 ms 135692 KB Output is correct
15 Correct 503 ms 246856 KB Output is correct
16 Correct 508 ms 248700 KB Output is correct
17 Correct 317 ms 140256 KB Output is correct
18 Correct 307 ms 140380 KB Output is correct
19 Correct 512 ms 256612 KB Output is correct
20 Correct 525 ms 256724 KB Output is correct