제출 #364521

#제출 시각아이디문제언어결과실행 시간메모리
364521daniel920712운세 보기 2 (JOI14_fortune_telling2)C++14
35 / 100
3086 ms259740 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; map < int , int > cha; set < int > have; struct A { int l,r; int nxl,nxr,nxt; int add; vector < pair < pair < int ,int > , int > > all; }Node[2400005]; struct B { int l,r; int nxl,nxr; int con; }Node2[2400005]; int now=1,now2=1; int Find(int x,int y,int here) { int t=0; if(upper_bound(Node[here].all.begin(),Node[here].all.end(),make_pair(make_pair(y+1,(int) -1),(int) -1))==Node[here].all.begin()) t=0; else { auto a=*prev(upper_bound(Node[here].all.begin(),Node[here].all.end(),make_pair(make_pair(y+1,(int) -1),(int) -1))); if(a.first.first<=y&&a.first.second>=y) t+=a.second; } if(Node[here].l==Node[here].r) return t; if(x<=(Node[here].l+Node[here].r)/2) t+=Find(x,y,Node[here].nxl); else t+=Find(x,y,Node[here].nxr); return t; } int Find2(int l,int r,int here) { int t=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) add2(where,Node2[here].nxl); else add2(where,Node2[here].nxr); } void add(int l1,int r1,int l2,int r2,int con,int here) { int t; if(l1==Node[here].l&&r1==Node[here].r) { Node[here].all.push_back(make_pair(make_pair(l2,r2),con)); return; } if(r1<=(Node[here].l+Node[here].r)/2) add(l1,r1,l2,r2,con,Node[here].nxl); else if(l1>(Node[here].l+Node[here].r)/2) add(l1,r1,l2,r2,con,Node[here].nxr); else { add(l1,(Node[here].l+Node[here].r)/2,l2,r2,con,Node[here].nxl); add((Node[here].l+Node[here].r)/2+1,r1,l2,r2,con,Node[here].nxr); } } void BFS(int here) { sort(Node[here].all.begin(),Node[here].all.end()); if(Node[here].l==Node[here].r) return ; BFS(Node[here].nxl); BFS(Node[here].nxr); } void build(int l,int r,int here) { Node[here].l=l; Node[here].r=r; Node[here].add=0; if(l==r) return; Node[here].nxl=now++; Node[here].nxr=now++; build(l,(l+r)/2,Node[here].nxl); build((l+r)/2+1,r,Node[here].nxr); } void build2(int l,int r,int here) { Node2[here].l=l; Node2[here].r=r; Node2[here].con=0; if(l==r) return; Node2[here].nxl=now2++; Node2[here].nxr=now2++; build2(l,(l+r)/2,Node2[here].nxl); build2((l+r)/2+1,r,Node2[here].nxr); } 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); have.insert(1e9+5); have.insert(1e9+6); have.insert(0); have.insert(1); build(0,1e6+5,0); build2(0,1e6+5,0); for(i=0;i<N;i++) { scanf("%d %d",&x[i],&y[i]); have.insert(x[i]); have.insert(y[i]); } for(i=1;i<=K;i++) { scanf("%d",&all[i].first); have.insert(all[i].first); have.insert(all[i].first+1); all[i].second=i; } vis.insert(0); vis.insert(1e9+5); for(auto i:have) cha[i]=ttt++; for(i=K;i>=1;i--) { con=0; con2=0; con=Find2(cha[all[i].first+1],cha[1e9+5],0); if(vis.find(all[i].first)!=vis.end()) { add2(cha[all[i].first],0); continue; } //printf("%lld\n",all[j]) //if(con!=con2) return 1; tt=*vis.upper_bound(all[i].first); tt2=*prev(vis.upper_bound(all[i].first)); if(con%2==0) { a.push_back(make_pair(make_pair(cha[all[i].first+1],cha[tt]),make_pair(cha[tt2+1],cha[all[i].first]))); b.push_back(make_pair(make_pair(cha[tt2+1],cha[all[i].first]),make_pair(cha[all[i].first+1],cha[tt]))); } else { b.push_back(make_pair(make_pair(cha[all[i].first+1],cha[tt]),make_pair(cha[tt2+1],cha[all[i].first]))); a.push_back(make_pair(make_pair(cha[tt2+1],cha[all[i].first]),make_pair(cha[all[i].first+1],cha[tt]))); } vis.insert(all[i].first); add2(cha[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(cha[all[i].first+1],cha[all[i-1].first]),make_pair(cha[all[i].first+1],cha[all[i-1].first]))); else b.push_back(make_pair(make_pair(cha[all[i].first+1],cha[all[i-1].first]),make_pair(cha[all[i].first+1],cha[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); BFS(0); for(i=0;i<N;i++) { ok=0; ok=Find(cha[x[i]],cha[y[i]],0); if(ok==1000000000) ans+=(long long)y[i]; else if(ok==1) ans+=(long long)x[i]; else while(1); } printf("%lld\n",ans); return 0; }

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

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