Submission #543295

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543295	2022-03-30T04:39:12 Z	karthikhegde05	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	4 ms	1108 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<<": ";
}

const int SZ = 1<<17;
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){
            val = (R-L+1)*lazy;
            if(L!=R){
                FOR(i, 0, 1){
                if(!c[i])c[i] = new node();  
                c[i]->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 (hi <= M) {
			if (!c[0]) c[0] = new node();
			c[0]->upd(lo, hi,v, L,M);
		} else if(lo>M){
			if (!c[1]) c[1] = new node();
			c[1]->upd(lo, hi,v, M+1,R);
		}
        else{
            if(!c[0])c[0] = new node();
            c[0]->upd(lo, hi, v, L, M);
            if(!c[1])c[1] = new node();
            c[1]->upd(lo, hi, v, M+1, R);

        }

        if(c[0]!=NULL)c[0]->push(L, M);
        if(c[1]!=NULL)c[1]->push(M+1, R);
        
		val = 0; 
        FOR(i,0, 1){
            if (c[i]!=NULL) 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])c[0] = new node();
        if(!c[1])c[1] = new node();
		if (c[0]) res += c[0]->query(lo,hi,L,M);
		if (c[1]) 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, y+c);
            cout<<c<<"\n";
        }
        else{
            seg->upd(x+c, y+c, 1);
        }
    }
    

    return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Incorrect	4 ms	1108 KB	Output isn't correct
5	Halted	0 ms	0 KB	-