Submission #789166

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
789166	2023-07-21T06:54:19 Z	yfrank792	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	2000 ms	8972 KB

apple

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef queue<int> qi;

#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair
#define FOR(i,a,b) for (int i=a; i<=b; i++)
#define FOR_(i,a,b,x) for (int i=a; i<=b; i+=x)
#define FOR_x(x,v) for (auto x : v)

const int INF = 0x3f3f3f3f;
const int maxn = 1e5+1;
const ll MOD = 10e7;

//? link: https://oj.uz/problem/view/IZhO12_apple

//? sol: dynamic/sparse segtree + lazy propagation

//! INCORRECT
//? FIXED
//      -> probably something wrong with update, cause repeated queries fixes the problem
//      -> mostly edited from template, later altered a bit according to official SOL

const int SZ = 1e9;         // max size of tree
template<class T> struct node {     // T = type parameter -> any type
    T val=0, lazy=0;
    T lr, rr;                       // lr=left range, rr=right range
    node<T>* lc;                    // lc = left child; * = pointer
    node<T>* rc;                    // rc = right child
    node(T lrr, T rrr) {            // constructor
        lc = rc = NULL;
        lr = lrr, rr = rrr; 
    }
    // inline T get_val() { return (lazy ? rr-lr+1 : val); }
    inline T get_val() { return val; }
    void push_lazy() {
        if (lazy) {
            val = rr-lr+1;
            lazy = 0;
            if (val==1) return;
            int mid = (lr+rr)>>1;
            if (!lc) lc=new node(lr,mid);
            if (!rc) rc=new node(mid+1,rr);
            lc->lazy = rc->lazy = 1;
        }
    }
    void update(int l, int r) {      // update node value
        push_lazy();
        int s = lr, t = rr;
        if (l<=s && t<=r) {
            lazy = 1;
            push_lazy();
            return;
        }
        int mid = (s+t)>>1;
        if (l<=mid) {
            if (!lc) lc=new node(s,mid);
            lc -> update(l, r);
        }
        if (r>mid) {
            if (!rc) rc=new node(mid+1,t);
            rc -> update(l, r);
        }
        if (lc) lc -> push_lazy();
        if (rc) rc -> push_lazy();
        val = (lc ? lc->get_val() : 0) + (rc ? rc->get_val() : 0);
        // printf("%d:%d -> %d\n",s,t,val);
        // push_lazy();
    }
    T query(int l, int r) {
        int s = lr, t = rr;
        push_lazy();
        // cout << lr << " " << rr << " " << val << " " << lazy << endl;
        if (l<=s && t<=r) return val;
        int mid = (s+t)>>1;
        T cnt = 0;
        if (l<=mid) {
            if (!lc) lc = new node(s,mid);
            cnt += lc->query(l,r);
        }
        if (r>mid) {
            if (!rc) rc = new node(mid+1,t);
            cnt += rc->query(l,r);
        }
        return cnt;
    }
    void debugQ(int level) {
        // cout << level << " " << lr << " " << rr << " " << val << " " << lazy << endl;
        if (lc) lc->debugQ(level+1);
        if (rc) rc->debugQ(level+1);
    }
};

int m, c=0;
node<int> root(1,SZ);     // root node

int main()
{
    // faster cin/cout
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> m;
    while (m--) {
        int d,x,y; cin>>d>>x>>y;
        if (d==1) {
            root.debugQ(0);
            c = root.query(x+c,y+c);
            cout << c << endl;
        }
        else {
            root.update(x+c,y+c);
            // FOR(i,1,10) cout << root.query(i,i) << " ";
            // cout << endl;
        }
    }

    return 0;   
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	320 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1514 ms	7764 KB	Output is correct
5	Execution timed out	2055 ms	8972 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-