Submission #858435

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
858435	2023-10-08T13:35:22 Z	Requiem	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	379 ms	262144 KB

apple

#include<bits/stdc++.h>
#define int long long
#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;
struct SparseSegmentTree{
    int sum,lazy,l,r;
    SparseSegmentTree *toleft=NULL, *toright=NULL;
    SparseSegmentTree(): sum(0), lazy(-1), l(0), r(0) {}
    SparseSegmentTree(int l,int r): sum(0), lazy(-1), l(l), r(r){}
};
int cnt = 0;
SparseSegmentTree *root;
void push(SparseSegmentTree *root){
    if (root!=NULL){
        int mid = (root->l + root->r) / 2;
        if (root->toleft == NULL) root->toleft = new SparseSegmentTree(root->l,mid);
        if (root->toright == NULL) root->toright = new SparseSegmentTree(mid+1,root->r);
        if (root->lazy==1){
            root->sum = root->r  -  root->l +1;
            root->toleft->lazy = root->lazy;
            root->toright->lazy = root->lazy;
            root->lazy = -1;
        }
    }
}
void upd(SparseSegmentTree *root,int u,int v){
    push(root);
    if (root->l > v or root->r < u) return;
    if (root->l >= u and root->r <=v) {
        root->lazy = 1;
        push(root);
        return;
    }
    upd(root->toleft,u,v);
    upd(root->toright,u,v);
    root->sum = root->toleft->sum + root->toright->sum;
}
int get(SparseSegmentTree *root,int u,int v){
    push(root);
    if (root->l > v or root->r < u) return 0;
    if (root->l >= u and root->r <=v) return root->sum;
    return get(root->toleft,u,v) + get(root->toright,u,v);
}
int n;
main()
{
    fast;
  //  freopen(TASKNAME".inp","r",stdin);
  //  freopen(TASKNAME".out","w",stdout);
    int n;
    cin>>n;
    int c = 0;
    root = new SparseSegmentTree(1,1e9);
    for(int i=1;i<=n;i++){
        int type,x,y;
        cin>>type>>x>>y;
        if (type==1) {
            c = get(root,x+c,y+c);
            cout<<c<<endl;
        }
        else{
            upd(root,x+c,y+c);
        }
    }

}

Compilation message

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

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	16 ms	12612 KB	Output is correct
5	Correct	20 ms	15196 KB	Output is correct
6	Correct	19 ms	14684 KB	Output is correct
7	Correct	19 ms	15184 KB	Output is correct
8	Correct	162 ms	116680 KB	Output is correct
9	Correct	334 ms	202392 KB	Output is correct
10	Correct	343 ms	223828 KB	Output is correct
11	Correct	367 ms	240472 KB	Output is correct
12	Correct	379 ms	248100 KB	Output is correct
13	Runtime error	313 ms	262144 KB	Execution killed with signal 9
14	Halted	0 ms	0 KB	-