Submission #1015593

#TimeUsernameProblemLanguageResultExecution timeMemory
1015593andrei_iorgulescuFortune Telling 2 (JOI14_fortune_telling2)C++14
35 / 100
3035 ms9296 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx2") using namespace std; int n,k,a[200005],b[200005],t[200005]; int g; bool tr[305][305]; vector<int> lol; short int pa[200005],pb[200005]; pair<int,int> vv[400005]; bool sp[200005]; int f1[400005],f2[400005]; int vls[305],pvls; int opp[305],nrop; bool incerc[305][305]; void solve(vector<int> op) { nrop = 0; for (auto it : op) opp[nrop++] = it; set<int> ss; for (auto it : op) ss.insert(it); pvls = 0; for (auto it : ss) vls[pvls++] = it; vls[pvls++] = (int)2e9; int i0 = 0; for (int i = 1; i <= 2 * n; i++) { while (vls[i0] < f1[i]) i0++; if (f2[i] < 0) { if (!sp[-f2[i]]) pb[-f2[i]] = i0; else pa[-f2[i]] = i0; } else { if (!sp[f2[i]]) pa[f2[i]] = i0; else pb[f2[i]] = i0; } } for (int i = 0; i < pvls; i++) for (int j = 0; j < pvls; j++) incerc[i][j] = false; for (int i = 1; i <= n; i++) incerc[pa[i]][pb[i]] = true; for (int i = 0; i < pvls; i++) { for (int j = 0; j < pvls; j++) { if (!incerc[i][j]) continue; int x = vls[i],y = vls[j]; bool cnt_swap = false; for (int q = 0; q < nrop; q++) { if (opp[q] >= x) swap(x,y),cnt_swap ^= 1; } if (cnt_swap) tr[i][j] = true; else tr[i][j] = false; } } for (int i = 1; i <= n; i++) { if (tr[pa[i]][pb[i]]) sp[i] ^= 1; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i] >> b[i]; for (int i = 1; i <= k; i++) cin >> t[i]; for (int i = 1; i <= n; i++) { vv[2 * i - 1] = {a[i],i}; vv[2 * i] = {b[i],-i}; } sort(vv + 1,vv + 2 * n + 1); for (int i = 1; i <= 2 * n; i++) { f1[i] = vv[i].first; f2[i] = vv[i].second; } g = 150; for (int i = 1; i <= k; i += g) { vector<int> op; for (int j = i; j <= k and j < i + g; j++) op.push_back(t[j]); solve(op); } long long ans = 0; for (int i = 1; i <= n; i++) if (sp[i]) swap(a[i],b[i]); for (int i = 1; i <= n; i++) ans += a[i]; cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...