Submission #858464

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858464	2023-10-08T14:01:12 Z	Requiem	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	214 ms	153056 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 = 1e5 + 9;
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	28 ms	150608 KB	Output is correct
2	Correct	27 ms	150608 KB	Output is correct
3	Correct	27 ms	150584 KB	Output is correct
4	Correct	38 ms	150624 KB	Output is correct
5	Correct	37 ms	150620 KB	Output is correct
6	Correct	39 ms	150608 KB	Output is correct
7	Correct	37 ms	150612 KB	Output is correct
8	Correct	100 ms	150872 KB	Output is correct
9	Correct	200 ms	151284 KB	Output is correct
10	Correct	214 ms	151124 KB	Output is correct
11	Correct	197 ms	151092 KB	Output is correct
12	Correct	207 ms	151336 KB	Output is correct
13	Correct	174 ms	151120 KB	Output is correct
14	Correct	174 ms	151240 KB	Output is correct
15	Incorrect	185 ms	153056 KB	Output isn't correct
16	Halted	0 ms	0 KB	-