Submission #884923

#	Time	Username	Problem	Language	Result	Execution time	Memory
884923		MarwenElarbi	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	1 ms	4956 KiB

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define vi vector<int>
#define ve vector
#define ll long long
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define onbit __builtin_popcount
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
using namespace __gnu_pbds;
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll MOD = 1e9+7;
const int nax = 2e5+5;
const int MAX_VAL = 1e5+1;
double PI=3.14159265359;
int arx[8]={1,0,0,-1,-1,-1, 1, 1};
int ary[8]={0,1,-1, 0, 1,-1,-1, 1};
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
int cnt=0;
struct Node{
    int sum, lazy, left, right, tl, tr;
    Node(): sum(0), lazy(0), left(-1), right(-1) {}
};
Node segtree[nax];
void expand(int pos){
    if(segtree[pos].lazy==1){
        segtree[pos].sum=segtree[pos].tr-segtree[pos].tl+1;
        int mid=(segtree[pos].tl+segtree[pos].tr)/2;
        if(segtree[pos].left==-1){
            segtree[pos].left=++cnt;
            segtree[segtree[pos].left].tl=segtree[pos].tl;
            segtree[segtree[pos].left].tr=mid;
        }
        if(segtree[pos].right==-1){
            segtree[pos].right=++cnt;
            segtree[segtree[pos].right].tl=mid+1;
            segtree[segtree[pos].right].tr=segtree[pos].tr;
        }
        segtree[segtree[pos].left].lazy=segtree[segtree[pos].right].lazy=1;
    }
    segtree[pos].lazy=0;
}
void update(int pos,int l,int r){
    expand(pos);
    //cout<<pos<<" "<<segtree[pos].tl<<" "<<segtree[pos].tr<<endl;
    if(segtree[pos].tl==l&&segtree[pos].tr==r){
        segtree[pos].lazy=1;
        expand(pos);
        return;
    }
    int mid=(segtree[pos].tl+segtree[pos].tr)/2;
    if(segtree[pos].left==-1){
        segtree[pos].left=++cnt;
        segtree[segtree[pos].left].tl=segtree[pos].tl;
        segtree[segtree[pos].left].tr=mid;
    }
    if(segtree[pos].right==-1){
        segtree[pos].right=++cnt;
        segtree[segtree[pos].right].tl=mid+1;
        segtree[segtree[pos].right].tr=segtree[pos].tr;
    }
    if(l>mid) update(segtree[pos].right,l,r);
    else if (r<=mid) update(segtree[pos].left,l,r);
    else{
        update(segtree[pos].left,l,mid);
        update(segtree[pos].right,mid+1,r);
    }
    expand(segtree[pos].left);
    expand(segtree[pos].right);
    segtree[pos].sum=segtree[segtree[pos].left].sum+segtree[segtree[pos].right].sum;
    return;
}
int query(int pos,int l,int r){
    expand(pos);
    if(segtree[pos].tl==l&&segtree[pos].tr==r){
        return segtree[pos].sum;
    }
    int mid=(segtree[pos].tl+segtree[pos].tr)/2;
    if(segtree[pos].left==-1){
        segtree[pos].left=++cnt;
        segtree[segtree[pos].left].tl=segtree[pos].tl;
        segtree[segtree[pos].left].tr=mid;
    }
    if(segtree[pos].right==-1){
        segtree[pos].right=++cnt;
        segtree[segtree[pos].right].tl=mid+1;
        segtree[segtree[pos].right].tr=segtree[pos].tr;
    }
    if(l>mid) return query(segtree[pos].right,l,r);
    else if (r<=mid) return query(segtree[pos].left,l,r);
    else{
        return query(segtree[pos].left,l,mid)+query(segtree[pos].right,mid+1,r);
    }
}
int main(){
    optimise;
    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    //setIO("snowcow");
    int n;
    cin>>n;
    int lst=0;
    segtree[0].sum=0;
    segtree[0].lazy=0;
    segtree[0].tl=0;
    segtree[0].tr=1e9;
    for (int i = 0; i < n; ++i)
    {
        int c;
        cin>>c;
        if(c==1){
            int l,r;
            cin>>l>>r;
            l+=lst;
            r+=lst;
            int a=query(0,l,r);
            cout <<a<<endl;
            lst+=a;
        }else{
            int l,r;
            cin>>l>>r;
            l+=lst;
            r+=lst;
            update(0,l,r);
        }
    }
    return 0;
}

Compilation message (stderr)

apple.cpp: In function 'void setIO(std::string)':
apple.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
apple.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100