Submission #945274

#TimeUsernameProblemLanguageResultExecution timeMemory
945274tsetFortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
9 ms41048 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int T = 1048576; const int INF = 1e18; vector<int > ab; void upd(int nde) { ab[nde] = max(ab[nde *2], ab[nde*2 +1]); if(nde > 1) upd(nde /2); } void setValue(int nde, int val) { ab[nde+T] = val; upd((nde+T)/2); } int query(int nde, int RB, int RE, int GB, int GE) { if(GB > RE || RB > GE) return -INF; if(RB >= GB && RE <= GE) return ab[nde]; int mid = (RB + RE)/2; return max(query(nde *2, RB, mid, GB, GE), query(nde*2 +1, mid+1, RE, GB, GE)); } vector<int > ab2; void upd2(int nde) { ab2[nde] = ab2[nde *2] + ab2[nde*2 +1]; if(nde > 1) upd(nde /2); } void addRange(int nde, int RB, int RE, int GB, int GE, int val) { //printf("%lld %lld %lld %lld %lld %lld \n", nde, RB, RE, GB, GE, val); if(GB > RE || RB > GE) return; if(RB >= GB && RE <= GE) { ab2[nde] += val; return; } int mid = (RB + RE)/2; addRange(nde *2, RB, mid, GB, GE, val); addRange(nde*2 +1, mid+1, RE, GB, GE, val); } int getValue(int pos) { int ans = 0; pos += T; while (pos >= 1) { ans += ab2[pos]; pos/=2; } return ans; } signed main() { int N, K; scanf("%lld%lld", &N, &K); vector<pair<int, int>> data; vector<int > queries(K); vector<int> original(1000000); map<int, int> compressed; set<int> values; for(int iN = 0; iN < N; iN ++) { int Ai, Bi; scanf("%lld %lld", &Ai, &Bi); data.push_back({Ai, Bi}); values.insert(Ai); values.insert(Bi); } for(int iQ = 0; iQ< K; iQ++) { int Ti; scanf("%lld", &Ti); queries[iQ] = Ti; values.insert(Ti); } int idAct = 1; for(int val : values) { compressed[val] = idAct; original[idAct] = val; idAct+=2; } vector<int> rotaInit(N, 0); vector<pair<int, int>> inters; vector<pair<int, int> > whenStop; vector<pair<int, int>> cards(N); vector<int> ans(N, -INF); ab.assign(2*T, -INF); ab2.assign(2*T, 0); for(int iK = 0; iK<K; iK++) { queries[iK] = compressed[queries[iK]]; setValue(queries[iK], iK); } for(int iN = 0; iN< N; iN++) { int deb = compressed[data[iN].first]; int fin = compressed[data[iN].second]; if(deb > fin) { swap(deb, fin); rotaInit[iN]++; } cards[iN] = {deb, fin}; int lastMX = query(1, 0, T-1, deb, fin-1); if(lastMX!=-INF) { //printf("card %lld : last end = query nu. %lld\n", iN, lastMX); whenStop.push_back({lastMX, iN}); } } sort(whenStop.begin(), whenStop.end(), greater<pair<int, int>>()); int posiWS = 0; for(int iQ = K-1; iQ >= 0; iQ--) { while (posiWS< whenStop.size() && whenStop[posiWS].first == iQ) { int iN = whenStop[posiWS].second; ans[iN]=getValue(compressed[max(cards[iN].first, cards[iN].second)])+1;//+1 bc on commence au max instant //printf("ans[%lld]=%lld\n", iN, ans[iN]); posiWS++; } addRange(1, 0, T-1, 0, queries[iQ], 1); } int ansTot = 0; for(int iN=0; iN<N; iN++) { if(ans[iN]==-INF) { ans[iN] = rotaInit[iN] + getValue(compressed[max(data[iN].first, data[iN].second)]); } //printf("%lld:%lld | %lld/%lld\n", iN, ans[iN], original[cards[iN].first], original[cards[iN].second]); if(ans[iN]%2 == 0) ansTot += original[cards[iN].first]; else ansTot += original[cards[iN].second]; } printf("%lld\n", ansTot); }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:137:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         while (posiWS< whenStop.size() && whenStop[posiWS].first == iQ)
      |                ~~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%lld%lld", &N, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%lld %lld", &Ai, &Bi);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         scanf("%lld", &Ti);
      |         ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...