Submission #647708

#TimeUsernameProblemLanguageResultExecution timeMemory
647708Ronin13Fortune Telling 2 (JOI14_fortune_telling2)C++14
100 / 100
1424 ms75120 KiB
#include<bits/stdc++.h> #define ll long long #define ull unsigned ll #define f first #define s second #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define epb emplace_back using namespace std; int lsb(int x){ return x & -x; } const int NMAX = 1e6 + 1; vector <int> bit(NMAX); int n; void add(int v, int val){ while(v < NMAX){ bit[v] += val; v += lsb(v); } } int get(int pos){ int sum = 0; while(pos){ sum += bit[pos]; pos -= lsb(pos); } return sum; } int sum(int l, int r){ return get(r) - get(l - 1); } vector <int> t(4 * NMAX); void update(int v, int l, int r, int pos, int val){ if(l > pos || r < pos) return; if(l == r){ t[v] = max(val, t[v]); return; } int m = (l + r) / 2; update(2 * v, l, m, pos, val); update(2 * v + 1, m + 1, r, pos, val); t[v] = max(t[2 * v], t[2 * v + 1]); } int get(int v, int l, int r, int st, int fin){ if(l > fin || r < st) return 0; if(l >= st && r <= fin) return t[v]; int m = (l + r) / 2; return max(get(2 * v, l, m, st, fin), get(2 * v + 1, m + 1, r, st, fin)); } map <int,int> mp; int main(){ cin >> n; int k; cin >> k; int a[n + 1], b[n + 1]; int cur[n + 1]; vector <int> vec; for(int i= 1; i<= n; i++){ cin >> a[i] >> b[i]; vec.pb(a[i]); vec.pb(b[i]); if(a[i] <= b[i]) cur[i] = 1; else cur[i] = 0; } int t[k + 1]; for(int i = 1; i <= k; i++) cin >> t[i]; for(int i = 1; i <= k; i++) vec.pb(t[i]); sort(vec.begin(), vec.end()); for(int i = 0; i < vec.size(); i++){ int x = vec[i]; mp[x] = i + 1; } for(int i = k; i >= 1; i--){ int v = t[i]; v = mp[v]; update(1, 1, 2 * n + k, v, i); } ll ans = 0; vector <vector <int> > qv(2 * n + k + 1); for(int i = 1; i <= n; i++){ int v = min(a[i], b[i]); int u = max(a[i], b[i]); int x = mp[v], y = mp[u]; y--; int val = get(1, 1, 2 * n + k, x, y); //cout << val << "\n"; qv[val].pb(i); } for(int i = k; i >= 1; i--){ int x= t[i]; x = mp[x]; add(x, 1); for(int to : qv[i]){ int r = max(b[to], a[to]); r= mp[r]; int v = sum(r, NMAX - 1); //cout << v << ' ' ; if(v % 2 == 0) ans += (ll)max(b[to], a[to]); else ans += (ll)min(b[to], a[to]); } //cout << "\n"; } for(int to : qv[0]){ int r = max(b[to], a[to]); r = mp[r]; int v = sum(r, NMAX - 1); v += cur[to]; if(v & 1) ans += (ll)min(b[to], a[to]); else ans += (ll)max(b[to], a[to]); } cout << ans; return 0; }

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 0; i < vec.size(); i++){
      |                    ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...