제출 #163926

#제출 시각아이디문제언어결과실행 시간메모리
163926TadijaSebez절취선 (JOI14_ho_t5)C++11
0 / 100
2 ms380 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mt make_tuple 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) { 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 pull(x); } else { Ins(ls[x],v); if(pri[ls[x]]>pri[x]) rot_r(x); else 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 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()); for(auto e:events) { int x,t,i;tie(x,t,i)=e; if(t==1) { } if(t==2) { } if(t==3) { } } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:70: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:73: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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...