제출 #364558

#제출 시각아이디문제언어결과실행 시간메모리
364558daniel920712운세 보기 2 (JOI14_fortune_telling2)C++14
35 / 100
3071 ms125200 KiB
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <vector> #include <algorithm> #include <string.h> #include <map> #include <vector> #include <set> using namespace std; int x[200005],y[200005]; pair < int , int > all[200005]; vector < pair < pair < int , int > , pair < int , int > > > a,b; bool F(pair < int , int > a,pair < int , int > b) { if(a.first>b.first) return 1; if(a.first<b.first) return 0; return a.second<b.second; } set < int > vis,have; vector < int > Cha; map < pair < int ,int > , int > all2; pair < pair < vector < pair < pair < int ,int > , int > > , vector < pair < pair < int ,int > , int > > > , vector < pair < int , pair < int , int > > > > query[1000005]; struct B { int l,r; int nxl,nxr; int con; }Node2[2000005]; int now=1,now2=1; void New2(int l,int r,int here) { Node2[here].l=l; Node2[here].r=r; Node2[here].con=0; Node2[here].nxl=-1; Node2[here].nxr=-1; } int Find(int y,int here) { int t=0; if(here==-1) return 0; if(all2.upper_bound((make_pair(y+1,(int) -1)))==all2.begin()) t=0; else { auto a=*prev(all2.upper_bound(make_pair(y+1,(int) -1))); if(a.first.first<=y&&a.first.second>=y) t+=a.second; } return t; } int Find2(int l,int r,int here) { int t=0; if(here==-1) return 0; t=0; if(l==Node2[here].l&&r==Node2[here].r) return Node2[here].con; if(r<=(Node2[here].l+Node2[here].r)/2) return Find2(l,r,Node2[here].nxl); else if(l>(Node2[here].l+Node2[here].r)/2) return Find2(l,r,Node2[here].nxr); else return Find2(l,(Node2[here].l+Node2[here].r)/2,Node2[here].nxl)+Find2((Node2[here].l+Node2[here].r)/2+1,r,Node2[here].nxr); } void add2(int where,int here) { Node2[here].con++; if(where==Node2[here].l&&where==Node2[here].r) return; if(where<=(Node2[here].l+Node2[here].r)/2) { if(Node2[here].nxl==-1) { Node2[here].nxl=now2++; New2(Node2[here].l,(Node2[here].l+Node2[here].r)/2,Node2[here].nxl); } add2(where,Node2[here].nxl); } else { if(Node2[here].nxr==-1) { Node2[here].nxr=now2++; New2((Node2[here].l+Node2[here].r)/2+1,Node2[here].r,Node2[here].nxr); } add2(where,Node2[here].nxr); } } int cha(int here) { return lower_bound(Cha.begin(),Cha.end(),here)-Cha.begin(); } void add(int l1,int r1,int l2,int r2,int con,int here) { l1=cha(l1); r1=cha(r1+1); query[l1].first.first.push_back(make_pair(make_pair(l2,r2),con)); query[r1].first.second.push_back(make_pair(make_pair(l2,r2),con)); } int main() { int N,K,i,j,con,ok=0,con2=0,tt,tt2,ttt=0; long long ans=0; scanf("%d %d",&N,&K); New2(0,1e9+5,0); for(i=0;i<N;i++) { scanf("%d %d",&x[i],&y[i]); have.insert(x[i]); } for(i=1;i<=K;i++) { scanf("%d",&all[i].first); all[i].second=i; have.insert(all[i].first); have.insert(all[i].first+1); } have.insert(0); have.insert(0+1); have.insert(1e9+5); have.insert(1e9+5+1); for(auto i:have) Cha.push_back(i); for(i=0;i<N;i++) query[cha(x[i])].second.push_back(make_pair(y[i],make_pair(x[i],y[i]))); vis.insert(0); vis.insert(1e9+5); for(i=K;i>=1;i--) { con=0; con2=0; con=Find2(all[i].first+1,1e9+1,0); for(j=i+1;j<=K;j++) if(all[j].first>all[i].first) con2++; if(vis.find(all[i].first)!=vis.end()) { add2(all[i].first,0); continue; } tt=*vis.upper_bound(all[i].first); tt2=*prev(vis.upper_bound(all[i].first)); if(con2%2==0) { a.push_back(make_pair(make_pair(all[i].first+1,tt),make_pair(tt2+1,all[i].first))); b.push_back(make_pair(make_pair(tt2+1,all[i].first),make_pair(all[i].first+1,tt))); } else { b.push_back(make_pair(make_pair(all[i].first+1,tt),make_pair(tt2+1,all[i].first))); a.push_back(make_pair(make_pair(tt2+1,all[i].first),make_pair(all[i].first+1,tt))); } vis.insert(all[i].first); add2(all[i].first,0); } all[0].first=1e9+5; all[0].second=0; sort(all+1,all+K+1,F); all[K+1].first=0; all[K+1].second=K+1; for(i=1;i<=K+1;i++) { con=0; con2=i; if(all[i].first!=all[i-1].first) { if(con2%2==1) a.push_back(make_pair(make_pair(all[i].first+1,all[i-1].first),make_pair(all[i].first+1,all[i-1].first))); else b.push_back(make_pair(make_pair(all[i].first+1,all[i-1].first),make_pair(all[i].first+1,all[i-1].first))); } } for(auto j:a) add(j.first.first,j.first.second,j.second.first,j.second.second,1,0); for(auto j:b) add(j.first.first,j.first.second,j.second.first,j.second.second,1e9,0); for(i=0;i<1000000;i++) { for(auto j:query[i].first.second) all2.erase(j.first); for(auto j:query[i].first.first) all2[j.first]=j.second; for(auto j:query[i].second) { if(Find(j.first,0)==1) ans+=j.second.first; else ans+=j.second.second; } } printf("%lld\n",ans); return 0; }

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

fortune_telling2.cpp: In function 'int Find2(int, int, int)':
fortune_telling2.cpp:56:9: warning: variable 't' set but not used [-Wunused-but-set-variable]
   56 |     int t=0;
      |         ^
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:101:17: warning: variable 'con' set but not used [-Wunused-but-set-variable]
  101 |     int N,K,i,j,con,ok=0,con2=0,tt,tt2,ttt=0;
      |                 ^~~
fortune_telling2.cpp:101:21: warning: unused variable 'ok' [-Wunused-variable]
  101 |     int N,K,i,j,con,ok=0,con2=0,tt,tt2,ttt=0;
      |                     ^~
fortune_telling2.cpp:101:40: warning: unused variable 'ttt' [-Wunused-variable]
  101 |     int N,K,i,j,con,ok=0,con2=0,tt,tt2,ttt=0;
      |                                        ^~~
fortune_telling2.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  103 |     scanf("%d %d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |         scanf("%d %d",&x[i],&y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |         scanf("%d",&all[i].first);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...