# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
872810 | AndreiBOTO | Monkey and Apple-trees (IZhO12_apple) | C++14 | 0 ms | 344 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma optimize GCC ("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
///#include <tryhardmode>
///#include <GODMODE::ON>
///Hey I heard you like the wild ones
///Wild Ones - Flo Rida, Sia
using namespace std;
const int INF=1e9;
struct SegTree{
public:
int s;
bool lazy;
SegTree *left;
SegTree *right;
SegTree()
{
s=0;
lazy=false;
left=right=NULL;
}
};
void propag(SegTree *aint,int st,int dr)
{
if(aint==NULL)
return ;
else
{
if(aint->lazy)
{
aint->s=dr-st+1;
if(st!=dr)
{
if(aint->left==NULL)
aint->left=new SegTree();
if(aint->right==NULL)
aint->right=new SegTree();
aint->left->lazy=true;
aint->right->lazy=true;
}
aint->lazy=false;
}
}
}
void update(SegTree *aint,int st,int dr,int a,int b)
{
propag(aint,st,dr);
if(a<=st && dr<=b)
{
aint->lazy=true;
aint->s=dr-st+1;
return ;
}
else
{
int mij=st+dr;
mij/=2;
if(aint->left==NULL)
aint->left=new SegTree();
if(aint->right==NULL)
aint->right=new SegTree();
if(a<=mij)
update(aint->left,st,mij,a,b);
if(mij<b)
update(aint->right,mij+1,dr,a,b);
aint->s=(aint->left->s)+(aint->right->s);
}
}
int query(SegTree *aint,int st,int dr,int a,int b)
{
if(aint==NULL)
return 0;
propag(aint,st,dr);
if(a<=st && dr<=b)
return aint->s;
else
{
int kon=0;
int mij=st+dr;
mij/=2;
if(a<=mij)
return query(aint->left,st,mij,a,b);
if(mij<b)
return query(aint->right,mij+1,dr,a,b);
kon+=query(aint->left,st,mij,a,b)+query(aint->right,mij+1,dr,a,b);
return kon;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
SegTree *aint=new SegTree();
int t,c=0;
cin>>t;
while(t--)
{
int type,x,y;
cin>>type>>x>>y;
if(type==1)
{
c=query(aint,1,INF,x+c,y+c);
cout<<c<<"\n";
}
else
update(aint,1,INF,x+c,y+c);
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |