Submission #62001

#TimeUsernameProblemLanguageResultExecution timeMemory
62001mohammedehab2002운세 보기 2 (JOI14_fortune_telling2)C++11
0 / 100
43 ms524 KiB
#include <iostream> #include <algorithm> using namespace std; #define BU 450 pair<int,int> p[200005]; int lim[200005],lazy[800005]; bool cmp(pair<int,int> a,pair<int,int> b) { return (a.second<b.second); } int merge(int x,int y) { if (!y) return x; if (!x) return y; if (y==-1) return 3-x; return y; } void update(int node,int st,int en,int l,int r,int f) { if (st!=en) { lazy[2*node]=merge(lazy[2*node],lazy[node]); lazy[2*node+1]=merge(lazy[2*node+1],lazy[node]); lazy[node]=0; } if (en<l || st>r || r<l) return; if (l<=st && en<=r) { lazy[node]=merge(lazy[node],f); return; } int mid=(st+en)/2; update(2*node,st,mid,l,r,f); update(2*node+1,mid+1,en,l,r,f); } long long query(int node,int st,int en,int idx) { if (st!=en) { lazy[2*node]=merge(lazy[2*node],lazy[node]); lazy[2*node+1]=merge(lazy[2*node+1],lazy[node]); lazy[node]=0; } if (st==en) return lazy[node]; else { int mid=(st+en)/2; if (st<=idx && idx<=mid) return query(2*node,st,mid,idx); return query(2*node+1,mid+1,en,idx); } } int main() { int n,k; scanf("%d%d",&n,&k); for (int i=0;i<n;i++) { scanf("%d%d",&p[i].first,&p[i].second); update(1,0,n-1,i,i,1); } sort(p,p+n); for (int i=0;i<n;i+=BU) lim[i]=p[min(i+BU,n)-1].first; for (int i=0;i<n;i+=BU) sort(p,p+min(BU,n-i),cmp); while (k--) { int x; scanf("%d",&x); for (int i=0;i<n;i+=BU) { if (lim[i]>x) { for (int j=i;j<min(i+BU,n);j++) { int tmp=query(1,0,n-1,j); if ((tmp==1 && p[j].first<=x) || (tmp==2 && p[j].second<=x)) update(1,0,n-1,j,j,-1); } break; } int st=i,en=min(i+BU,n)-1; while (st!=en) { int mid=(st+en+1)/2; if (p[mid].second<=x) st=mid; else en=mid-1; } update(1,0,n-1,i,st,-1); update(1,0,n-1,st+1,min(i+BU,n)-1,2); } } long long ans=0; for (int i=0;i<n;i++) { if (query(1,0,n-1,i)==1) ans+=p[i].first; else ans+=p[i].second; } printf("%lld",ans); }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~
fortune_telling2.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&p[i].first,&p[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...