답안 #543284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
543284	2022-03-30T03:36:04 Z	karthikhegde05	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	76 ms	185848 KB

apple

#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<<": ";
}


struct Node{
	int sum, lazy, tl, tr, lc, rc;
	Node(): sum(0), lazy(0), lc(-1), rc(-1){}
};


const int MAXN = 123456;
Node segtree[64*MAXN];
int cnt = 2;

void push_lazy(int node){
	if(segtree[node].lazy){
		segtree[node].sum += (segtree[node].tr - segtree[node].tl +1)*segtree[node].lazy;
		int mid = (segtree[node].tl + segtree[node].tr)/2;

		if(segtree[node].lc==-1){
			segtree[node].lc = cnt++;
			segtree[segtree[node].lc].tl = segtree[node].tl;
			segtree[segtree[node].lc].tr = mid;
		}
		if(segtree[node].rc==-1){
			segtree[node].rc = cnt++;
			segtree[segtree[node].rc].tl = mid+1;
			segtree[segtree[node].rc].tr = segtree[node].tr;
		}

		segtree[segtree[node].lc].lazy += segtree[node].lazy;
		segtree[segtree[node].rc].lazy += segtree[node].lazy;
		segtree[node].lazy = 0;
	}
}


void update(int node, int inc, int l, int r){
	push_lazy(node);
	if(l<=segtree[node].tl && segtree[node].tr<=r){
		segtree[node].lazy += inc;
		push_lazy(node);
		return;
	}

	int mid = (segtree[node].tl + segtree[node].tr)/2;
	if(segtree[node].lc==-1){
		segtree[node].lc = cnt++;
		segtree[segtree[node].lc].tl = segtree[node].tl;
		segtree[segtree[node].lc].tr = mid;
	}
	if(segtree[node].rc==-1){
		segtree[node].rc = cnt++;
		segtree[segtree[node].rc].tl = mid+1;
		segtree[segtree[node].rc].tr = segtree[node].tr;
	}

	if(l>mid){
		update(segtree[node].rc, inc, l, r);
	}
	else if(r<=mid){
		update(segtree[node].lc, inc, l, r);
	}

	else{
		update(segtree[node].lc, inc, l, r);
		update(segtree[node].rc, inc, l, r);
	}

	// push_lazy(segtree[node].lc);
	// push_lazy(segtree[node].rc);

	segtree[node].sum = segtree[segtree[node].lc].sum + segtree[segtree[node].rc].sum;
}


int query(int node, int l, int r){
	push_lazy(node);
	if(l<=segtree[node].tl && segtree[node].tr <= r)
		return segtree[node].sum;
	
	int mid = (segtree[node].tl + segtree[node].tr)/2;
	if(segtree[node].lc==-1){
		segtree[node].lc = cnt++;
		segtree[segtree[node].lc].tl = segtree[node].tl;
		segtree[segtree[node].lc].tr = mid;
	}
	if(segtree[node].rc==-1){
		segtree[node].rc = cnt++;
		segtree[segtree[node].rc].tl = mid+1;
		segtree[segtree[node].rc].tr = segtree[node].tr;
	}

	if(l>mid){
		return query(segtree[node].rc, l, r);
	}
	if(r<=mid){
		return query(segtree[node].lc, l, r);
	}


	return query(segtree[node].lc, l, r) + query(segtree[node].rc, l, r);
}

int main(){

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


    int m;cin>>m;

	segtree[1].sum = 0;segtree[1].lazy = 0;
	segtree[1].tl = 1; segtree[1].tr = 1e9;

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


    return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	74 ms	185848 KB	Output is correct
2	Correct	76 ms	185800 KB	Output is correct
3	Incorrect	73 ms	185740 KB	Output isn't correct
4	Halted	0 ms	0 KB	-