Submission #858468

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858468	2023-10-08T14:07:23 Z	Requiem	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	231 ms	186564 KB

apple

#include<bits/stdc++.h>
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "apple"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 123456;
struct SparseSegmentTree{
    int sum,lazy,l,r,toleft,toright;
    SparseSegmentTree(): sum(0), lazy(-1), l(0), r(0), toleft(0), toright(0){}
    SparseSegmentTree(int l,int r): sum(0), lazy(-1), l(l), r(r), toleft(0), toright(0){}
};
int cnt = 0;
SparseSegmentTree st[MAXN*64];
void push(int node){
        int mid = (st[node].l + st[node].r) / 2;
        if (st[node].toleft == 0) {
            st[node].toleft=++cnt;
            st[cnt] = SparseSegmentTree(st[node].l,mid);
        }
        if (st[node].toright == 0) {
            st[node].toright=++cnt;
            st[cnt] = SparseSegmentTree(mid+1,st[node].r);
        }
        if (st[node].lazy==1){
            st[node].sum = st[node].r - st[node].l +1;
            st[st[node].toleft].lazy = st[st[node].toright].lazy = 1;;
            st[node].lazy = -1;
        }
}
void upd(int node,int u,int v){
    push(node);
    if (st[node].l > v or st[node].r < u) return;
    if (st[node].l >= u and st[node].r <=v) {
        st[node].lazy = 1;
        push(node);
        return;
    }
    upd(st[node].toleft,u,v);
    upd(st[node].toright,u,v);
    st[node].sum = st[st[node].toleft].sum + st[st[node].toright].sum;
}
int get(int node,int u,int v){
    push(node);
    if (st[node].l > v or st[node].r < u) return 0;
    if (st[node].l >= u and st[node].r <=v) return st[node].sum;
    return get(st[node].toleft,u,v) + get(st[node].toright,u,v);
}
int n;
main()
{
    fast;
 //   freopen(TASKNAME".inp","r",stdin);
 //   freopen(TASKNAME".out","w",stdout);
    int n;
    cin>>n;
    int c = 0;
    cnt = 1;
    st[1] = SparseSegmentTree(1,1e9);
    for(int i=1;i<=n;i++){
        int type,x,y;
        cin>>type>>x>>y;
        if (type==1) {
            c = get(1,x+c,y+c);
            cout<<c<<endl;
        }
        else{
            upd(1,x+c,y+c);
        }
    }

}

Compilation message

apple.cpp:63:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   63 | main()
      | ^~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	185936 KB	Output is correct
2	Correct	33 ms	185976 KB	Output is correct
3	Correct	33 ms	185940 KB	Output is correct
4	Correct	41 ms	185948 KB	Output is correct
5	Correct	43 ms	185940 KB	Output is correct
6	Correct	43 ms	185796 KB	Output is correct
7	Correct	45 ms	186008 KB	Output is correct
8	Correct	104 ms	186116 KB	Output is correct
9	Correct	224 ms	186552 KB	Output is correct
10	Correct	201 ms	186260 KB	Output is correct
11	Correct	226 ms	186192 KB	Output is correct
12	Correct	210 ms	186564 KB	Output is correct
13	Correct	181 ms	186448 KB	Output is correct
14	Correct	191 ms	186452 KB	Output is correct
15	Incorrect	231 ms	186524 KB	Output isn't correct
16	Halted	0 ms	0 KB	-