Submission #50634

#TimeUsernameProblemLanguageResultExecution timeMemory
50634wzyFortune Telling 2 (JOI14_fortune_telling2)C++11
0 / 100
797 ms97140 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define pii pair<int,int> #define F first #define S second int readint(){ char a = 255; int x = 0; while(!(a >= '0' && a <= '9'))a = getchar(); while(a >= '0' && a <= '9') x = 10*x + (a - '0') , a = getchar(); return x; } struct card{ int a , b; bool flip = false; int ppos; } v[200005]; int n , k ; class BIT{ /* MAGIA DO GATINHO . ∧_∧  (。・ω・。)つ━☆・*。 ⊂   ノ    ・゜+.  しーJ   °。+ *´¨)          .• ´¸.•*´¨) ¸.•*¨)           (¸.•´ (¸.•'* ☆ */ public: void set_size(int n){ binary_index_tree.resize(n); } int get(int x){ if(x == 0) return 0; int s = 0; for(int i = x ; i > 0 ; i-=(i&-i)) s+= binary_index_tree[i]; return s; } void add(int x , int vl){ for(int i = x ; i < binary_index_tree.size() ; i+= (i&-i)) binary_index_tree[i] += vl; } private : vector<int> binary_index_tree; }; struct node{ node *left = nullptr , *right = nullptr; int rmqid = - 1; }; node *treex; int rmq(node *& tree , int x , int y ,int l = 0 , int r = 1000000009){ int mid = (l+r)/2; if(l == x && r == y){ return tree->rmqid; } if(y <= mid){ if(tree->left == nullptr) return -1; return rmq(tree->left, x , y , l, mid); } else if(x > mid){ if(tree->right == nullptr) return -1; return rmq(tree->right , x , y , mid + 1, r); } else{ int a = - 1 , b = - 1; if(tree->left != nullptr) a = rmq(tree->left , x , mid , l ,mid); if(tree->right != nullptr) b = rmq(tree->right , mid + 1 , y , mid + 1 , r); return max(a,b); } } void update(node *& tree , int x , int vl ,int l = 0 , int r = 1000000009){ int mid = (l+r)/2; if(l ==r && l ==x){ tree->rmqid = max(tree->rmqid , vl); return ; } if(x <=mid){ if(tree->left == nullptr) tree->left = new node(); update(tree->left , x , vl , l , mid); } else{ if(tree->right == nullptr) tree->right = new node(); update(tree->right , x, vl , mid + 1 , r); } int a = -1 , b = -1; if(tree->left != nullptr) a = tree->left->rmqid; if(tree->right != nullptr) b = tree->right->rmqid; tree->rmqid = max(a,b); } vector<pair<int,int> > sweep[200005]; long long ans = 0; int main(){ n = readint() , k = readint(); for(int i = 0 ; i < n ; i ++){ v[i].a = readint() , v[i].b = readint(); if(v[i].a > v[i].b) swap(v[i].a , v[i].b) , v[i].flip = 1; } treex = new node(); vector<pii> rw(k); for(int i = 0 ; i < k ; i ++){ rw[i].first = readint(); rw[i].second = i; update(treex , rw[i].first, rw[i].second); } BIT bitx; bitx.set_size(250000); sort(rw.begin() , rw.end()); for(int i = 0 ; i < n ; i++){ int pos = -1; if(v[i].a < v[i].b) pos = rmq(treex , v[i].a, v[i].b - 1); int l = 0 , r = k - 1; int a = -1; while(l<=r){ int mid = (l+r)/2; if(rw[mid].first >= v[i].b){ r = mid - 1; a = mid; } else l = mid + 1; } if(a != -1) sweep[a].pb(pair<int,int>(i , pos + 1)); else ans += (v[i].flip ? v[i].b : v[i].a); } for(int i = k - 1 ; i >= 0 ; i--){ bitx.add(rw[i].second + 1 , +1); for(int j = 0 ; j < sweep[i].size() ; j++){ pii u = sweep[i][j]; int L = bitx.get(200005) - bitx.get(u.second); if(u.second == 0){ L += v[u.first].flip; if(L%2){ ans += v[u.first].b; } else ans += v[u.first].a; } else{ if(L%2){ ans += v[u.first].a; } else ans += v[u.first].b; } } } printf("%lld\n" , ans); }

Compilation message (stderr)

fortune_telling2.cpp: In member function 'void BIT::add(int, int)':
fortune_telling2.cpp:42:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = x ; i < binary_index_tree.size() ; i+= (i&-i)) binary_index_tree[i] += vl;
                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:132:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < sweep[i].size() ; j++){
                   ~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...