Submission #543298

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
543298	2022-03-30T04:51:46 Z	karthikhegde05	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	4 ms	980 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){
                if(!c[0])c[0] = new node();  
                c[0]->lazy =  lazy;
                if(!c[1])c[1] =  new node();
                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();

		if (hi <= M) {
			c[0]->upd(lo, hi,v, L,M);
		} else if(lo>M){
			c[1]->upd(lo, hi,v, M+1,R);
		}
        else{
            c[0]->upd(lo, hi, v, L, M);
            c[1]->upd(lo, hi, v, M+1, R);
        }

        c[0]->push(L, M);
        c[1]->push(M+1, R);
        
		val = c[0]->val + c[1]->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(hi<=M)return c[0]->query(lo, hi, L, M);
        else if(lo>M)return c[1]->query(lo, hi, M+1, R);

		return c[0]->query(lo, hi, L, M) + c[1]->query(lo, hi, M+1, R);
	}
	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;
}

Compilation message

apple.cpp: In instantiation of 'T node<T>::query(int, int, int, int) [with T = int]':
apple.cpp:120:36:   required from here
apple.cpp:83:22: warning: unused variable 'res' [-Wunused-variable]
   83 |   int M = (L+R)/2; T res = 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	980 KB	Output isn't correct
5	Halted	0 ms	0 KB	-