| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 163932 |
2019-11-16T09:50:41 Z |
TadijaSebez |
None (JOI14_ho_t5) |
C++11 |
|
3 ms |
504 KB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mt make_tuple
#define ll long long
const int N=100050;
int X1[N],X2[N],Y1[N],Y2[N];
vector<tuple<int,int,int>> events;
int ls[N],rs[N],pri[N],val[N],tsz,root,sum[N],tag[N],fir[N],sz[N],L[N],R[N];
int Make(int v)
{
tsz++;
pri[tsz]=rand()^rand();
val[tsz]=v;
sz[tsz]=1;
fir[tsz]=1;
L[tsz]=R[tsz]=v;
return tsz;
}
void upd(int x){ if(x) sum[x]=sz[x],fir[x]=0,tag[x]=1;}
void push(int x){ if(tag[x]) upd(ls[x]),upd(rs[x]),tag[x]=0;}
void pull(int x)
{
if(!x) return;
sz[x]=sz[ls[x]]+1+sz[rs[x]];
sum[x]=sum[ls[x]]+(1-fir[x])+sum[rs[x]];
L[x]=ls[x]?L[ls[x]]:val[x];
R[x]=rs[x]?R[rs[x]]:val[x];
}
void rot_l(int &x){ int y=rs[x],z=ls[y];rs[x]=z;ls[y]=x;pull(x);pull(y);x=y;}
void rot_r(int &x){ int y=ls[x],z=rs[y];ls[x]=z;rs[y]=x;pull(x);pull(y);x=y;}
void Ins(int &x, int v)
{
if(!x) x=Make(v);
else
{
push(x);
if(val[x]<v)
{
Ins(rs[x],v);
if(pri[rs[x]]>pri[x]) rot_l(x);
}
else
{
Ins(ls[x],v);
if(pri[ls[x]]>pri[x]) rot_r(x);
}
pull(x);
}
}
void Del(int &x, int v)
{
if(!x) return;
push(x);
if(val[x]==v)
{
if(!ls[x]) x=rs[x];
else if(!rs[x]) x=ls[x];
else if(pri[ls[x]]>pri[rs[x]]) rot_r(x),Del(rs[x],v);
else rot_l(x),Del(ls[x],v);
}
else if(val[x]<v) Del(rs[x],v);
else Del(ls[x],v);
pull(x);
}
int Get(int x, int qs, int qe)
{
if(!x || L[x]>qe || R[x]<qs) return 0;
if(L[x]>=qs && R[x]<=qe) return sum[x];
push(x);
return Get(ls[x],qs,qe)+Get(rs[x],qs,qe);
}
void Mark(int x, int qs, int qe)
{
if(!x || L[x]>qe || R[x]<qs) return;
if(L[x]>=qs && R[x]<=qe) return upd(x);
push(x);
Mark(ls[x],qs,qe);
Mark(rs[x],qs,qe);
pull(x);
}
int Pre(int x, int v)
{
if(!x) return 0;
push(x);
if(val[x]<=v)
{
if(rs[x] && L[rs[x]]<=v) return Pre(rs[x],v);
else return x;
}
else return Pre(ls[x],v);
}
int main()
{
srand(time(0));
int n,m,q;
scanf("%i %i %i",&n,&m,&q);
for(int i=1;i<=q;i++)
{
scanf("%i %i %i %i",&X1[i],&Y1[i],&X2[i],&Y2[i]);
if(X1[i]==X2[i]) events.pb(mt(X1[i],2,i));
else events.pb(mt(X1[i],1,i)),events.pb(mt(X2[i],3,i));
}
sort(events.begin(),events.end());
ll a=0,b=0;
for(auto e:events)
{
int x,t,i;tie(x,t,i)=e;
if(t==1) Ins(root,Y1[i]);
if(t==2)
{
a+=Get(root,Y1[i],Y2[i]);
int node=Pre(root,Y2[i]);
int f=fir[node];
Mark(root,Y1[i],Y2[i]);
if(node && val[node]>=Y1[i] && Get(root,Y1[i],Y2[i])>1 && f) b++;
}
if(t==3) Del(root,Y1[i]);
}
ll ans=(a+1)-b;
printf("%lld\n",ans);
return 0;
}
Compilation message
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i %i",&n,&m,&q);
~~~~~^~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i %i %i %i",&X1[i],&Y1[i],&X2[i],&Y2[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
