제출 #375059

#제출 시각아이디문제언어결과실행 시간메모리
375059daniel920712Examination (JOI19_examination)C++14
100 / 100
1925 ms537948 KiB
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <vector> #include <algorithm> using namespace std; struct A { int l,r; int nxl,nxr,nxt; int sum; }Node[400*100005]; int ans[1000005]; int XX[300005]; int YY[300005]; vector < pair < pair < int , int > , int > > query[5][300005]; vector < int > all; int now=1; void New(int l,int r,int t,int here) { Node[here].l=l; Node[here].r=r; Node[here].sum=0; Node[here].nxl=-1; Node[here].nxr=-1; Node[here].nxt=t; } void cha(int x,int y,int here) { Node[here].sum++; if(Node[here].nxt==-2) { if(y==Node[here].l&&y==Node[here].r) return; if(y<=(Node[here].l+Node[here].r)/2) { if(Node[here].nxl==-1) { Node[here].nxl=now++; New(Node[here].l,(Node[here].l+Node[here].r)/2,-2,Node[here].nxl); } cha(x,y,Node[here].nxl); } else { if(Node[here].nxr==-1) { Node[here].nxr=now++; New((Node[here].l+Node[here].r)/2+1,Node[here].r,-2,Node[here].nxr); } cha(x,y,Node[here].nxr); } } else { if(Node[here].nxt==-1) { Node[here].nxt=now++; New(0,300000,-2,Node[here].nxt); } cha(x,y,Node[here].nxt); if(x==Node[here].l&&x==Node[here].r) return; else if(x<=(Node[here].l+Node[here].r)/2) { if(Node[here].nxl==-1) { Node[here].nxl=now++; New(Node[here].l,(Node[here].l+Node[here].r)/2,-1,Node[here].nxl); } cha(x,y,Node[here].nxl); } else { if(Node[here].nxr==-1) { Node[here].nxr=now++; New((Node[here].l+Node[here].r)/2+1,Node[here].r,-1,Node[here].nxr); } cha(x,y,Node[here].nxr); } } } int Find(int l1,int r1,int l2,int r2,int here) { if(here==-1) return 0; if(Node[here].nxt==-2) { if(l2==Node[here].l&&r2==Node[here].r) return Node[here].sum; if(r2<=(Node[here].l+Node[here].r)/2) return Find(l1,r1,l2,r2,Node[here].nxl); else if(l2>(Node[here].l+Node[here].r)/2) return Find(l1,r1,l2,r2,Node[here].nxr); else return Find(l1,r1,l2,(Node[here].l+Node[here].r)/2,Node[here].nxl)+Find(l1,r1,(Node[here].l+Node[here].r)/2+1,r2,Node[here].nxr); } else { if(l1==Node[here].l&&r1==Node[here].r) return Find(l1,r1,l2,r2,Node[here].nxt); if(r1<=(Node[here].l+Node[here].r)/2) return Find(l1,r1,l2,r2,Node[here].nxl); else if(l1>(Node[here].l+Node[here].r)/2) return Find(l1,r1,l2,r2,Node[here].nxr); else return Find(l1,(Node[here].l+Node[here].r)/2,l2,r2,Node[here].nxl)+Find((Node[here].l+Node[here].r)/2+1,r1,l2,r2,Node[here].nxr); } } int Cha(int x) { return lower_bound(all.begin(),all.end(),x)-all.begin(); } int main() { int N,M,i,j,x,y,z; scanf("%d %d",&N,&M); for(i=0;i<N;i++) { scanf("%d %d",&x,&y); all.push_back(x); all.push_back(y); all.push_back(x+y); XX[i]=x; YY[i]=y; //query[0][x].push_back(make_pair(make_pair(y,0),0)); } sort(all.begin(),all.end()); for(i=0;i<N;i++) { query[0][Cha(XX[i])].push_back(make_pair(make_pair(Cha(YY[i]),Cha(XX[i]+YY[i])),0)); } for(i=0;i<M;i++) { scanf("%d %d %d",&x,&y,&z); query[1][Cha(x)].push_back(make_pair(make_pair(Cha(y),Cha(z)),i)); //query[1][x].push_back(make_pair(make_pair(y,z),i)); } New(0,300000,-1,0); for(i=300000;i>=0;i--) { for(auto j:query[0][i]) cha(j.first.first,j.first.second,0); for(auto j:query[1][i]) ans[j.second]=Find(j.first.first,300000,j.first.second,300000,0); } for(i=0;i<M;i++) printf("%d\n",ans[i]); return 0; }

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

examination.cpp: In function 'int main()':
examination.cpp:110:15: warning: unused variable 'j' [-Wunused-variable]
  110 |     int N,M,i,j,x,y,z;
      |               ^
examination.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |     scanf("%d %d",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~
examination.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  114 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~
examination.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  129 |         scanf("%d %d %d",&x,&y,&z);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...