Submission #67310

#TimeUsernameProblemLanguageResultExecution timeMemory
67310dualityFortune Telling 2 (JOI14_fortune_telling2)C++11
100 / 100
393 ms120592 KiB
#include <bits/stdc++.h> using namespace std; // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- struct card { int a,b,f; }; bool comp(card a,card b) { return a.b > b.b; } card C[200000]; pii T[200000]; int tree[1 << 19]; int tree2[200001]; int build(int s,int e,int i) { if (s == e) { tree[i] = T[s].second; return tree[i]; } int mid = (s+e) / 2; tree[i] = max(build(s,mid,2*i+1),build(mid+1,e,2*i+2)); return tree[i]; } int query(int s,int e,int qs,int qe,int i) { if ((s > qe) || (e < qs)) return -1; else if ((s >= qs) && (e <= qe)) return tree[i]; int mid = (s+e) / 2; return max(query(s,mid,qs,qe,2*i+1),query(mid+1,e,qs,qe,2*i+2)); } int query2(int i) { int sum = 0; for (i++; i > 0; i -= i & (-i)) sum += tree2[i]; return sum; } int query2(int s,int e) { return query2(e) - query2(s-1); } int update2(int i,int num,int K) { for (i++; i <= K; i += i & (-i)) tree2[i] += num; return 0; } int main() { int i; int N,K; scanf("%d %d",&N,&K); for (i = 0; i < N; i++) { scanf("%d %d",&C[i].a,&C[i].b); if (C[i].a > C[i].b) swap(C[i].a,C[i].b),C[i].f = 1; } for (i = 0; i < K; i++) scanf("%d",&T[i].first),T[i].second = i; LLI sum = 0; int e = K-1; sort(C,C+N,comp); sort(T,T+K); build(0,K-1,0); for (i = 0; i < N; i++) { int s = lower_bound(T,T+K,make_pair(C[i].a,0))-T; while ((e >= 0) && (C[i].b <= T[e].first)) update2(T[e].second,1,K),e--; int l = query(0,K-1,s,e,0); if (l == -1) sum += (((K-s) & 1)^C[i].f) ? C[i].b:C[i].a; else sum += (query2(l,K-1) & 1) ? C[i].a:C[i].b; } printf("%lld\n",sum); return 0; }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:84:10: 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:86:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&C[i].a,&C[i].b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:89:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < K; i++) scanf("%d",&T[i].first),T[i].second = i;
                             ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...