Submission #858482

# Submission time Handle Problem Language Result Execution time Memory
858482 2023-10-08T14:38:36 Z Requiem Monkey and Apple-trees (IZhO12_apple) C++17
100 / 100
309 ms 240524 KB
#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 = 100002;
struct SparseSegmentTree{
    int sum,lazy,l,r,toleft,toright;
    SparseSegmentTree(): sum(0), lazy(0), l(0), r(0), toleft(0), toright(0){}
    SparseSegmentTree(int l,int r): sum(0), lazy(0), l(l), r(r), toleft(0), toright(0){}
};
int cnt = 0;
SparseSegmentTree st[MAXN*102];
void push(int node){
     if (st[node].lazy==1){
            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);
            }
            st[node].sum = st[node].r - st[node].l +1;
            st[st[node].toleft].lazy = st[st[node].toright].lazy = 1;;
            st[node].lazy = 0;
 
     }
}
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;
    }
    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);
    }
    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;
    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);
    }
    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:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   82 | main()
      | ^~~~
# Verdict Execution time Memory Grader output
1 Correct 41 ms 239956 KB Output is correct
2 Correct 42 ms 239948 KB Output is correct
3 Correct 42 ms 239952 KB Output is correct
4 Correct 50 ms 239928 KB Output is correct
5 Correct 53 ms 239956 KB Output is correct
6 Correct 52 ms 239884 KB Output is correct
7 Correct 59 ms 239980 KB Output is correct
8 Correct 139 ms 240008 KB Output is correct
9 Correct 220 ms 240140 KB Output is correct
10 Correct 227 ms 240348 KB Output is correct
11 Correct 213 ms 240212 KB Output is correct
12 Correct 222 ms 240312 KB Output is correct
13 Correct 191 ms 240292 KB Output is correct
14 Correct 198 ms 240296 KB Output is correct
15 Correct 309 ms 240524 KB Output is correct
16 Correct 273 ms 240208 KB Output is correct
17 Correct 191 ms 240452 KB Output is correct
18 Correct 205 ms 240464 KB Output is correct
19 Correct 272 ms 240344 KB Output is correct
20 Correct 268 ms 240456 KB Output is correct