Submission #123644

#TimeUsernameProblemLanguageResultExecution timeMemory
123644egorlifarPalembang Bridges (APIO15_bridge)C++17
63 / 100
484 ms26468 KiB
/* ЗАПУСКАЕМ ░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░ ▄███▀░◐░░░▌░░░░░░░ ░░░░▌░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▌░░░░░▐▄▄░░░░░ ░░░░▌░░░░▄▀▒▒▀▀▀▀▄ ░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄ ░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░▄▄▌▌▄▌▌░░░░░ */ #include <iostream> #include <complex> #include <vector> #include <string> #include <algorithm> #include <cstdio> #include <numeric> #include <cstring> #include <ctime> #include <cstdlib> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #include <list> #include <cmath> #include <bitset> #include <cassert> #include <queue> #include <stack> #include <deque> using namespace std; template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; } template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } #define sz(c) (int)(c).size() #define all(c) (c).begin(), (c).end() #define rall(c) (c).rbegin(), (c).rend() #define left left228 #define right right228 #define next next228 #define rank rank228 #define prev prev228 #define y1 y1228 #define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin) #define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout) #define files(FILENAME) read(FILENAME), write(FILENAME) #define pb push_back const string FILENAME = "input"; const int MAXN = 200228; int n, k; int l[MAXN], r[MAXN]; vector<int> fb[MAXN]; vector<int> fe[MAXN]; long long score[MAXN]; vector<int> vx; int where[MAXN]; vector<pair<int, int> > st; int ft = 0; set<pair<int, int> > fi, fj, f1i, f1j, f2i; int cnti = 0; int cntj = 0; long long sumi = 0; long long sumj = 0; int cnt1i = 0; int cnt1j = 0; long long sum1i = 0; long long sum1j = 0; vector<pair<pair<int, int>, int> > sti, stj; void addi(int id) { fi.insert({vx[r[id]], id}); sti.pb({{vx[r[id]], id}, 1}); sumi += vx[r[id]]; cnti++; } void addj(int id) { fj.insert({vx[l[id]], id}); stj.pb({{vx[l[id]], id}, 1}); sumj += vx[l[id]]; cntj++; } void delj(int id) { if (fj.find({vx[l[id]], id}) != fj.end()) { cntj--; sumj -= vx[l[id]]; stj.pb({{vx[l[id]], id}, -1}); fj.erase({vx[l[id]], id}); } else { if (f1j.find({vx[r[id]], id}) != f1j.end()) { stj.pb({{vx[r[id]], id}, -2}); f1j.erase({vx[r[id]], id}); } else { cnt1j--; sum1j -= vx[r[id]]; } } } void deli(int id) { if (fi.find({vx[r[id]], id}) != fi.end()) { cnti--; sumi -= vx[r[id]]; sti.pb({{vx[r[id]], id}, -1}); fi.erase({vx[r[id]], id}); } if (f1i.find({vx[l[id]], id}) != f1i.end()) { cnt1i--; sum1i -= vx[l[id]]; //cout << cnt1i << ' ' << sum1i << endl; sti.pb({{vx[l[id]], id}, -2}); f1i.erase({vx[l[id]], id}); } if (f2i.find({vx[r[id]], id}) != f2i.end()) { sti.pb({{vx[r[id]], id}, -3}); f2i.erase({vx[r[id]], id}); } } void updi(int x) { //cout << x << endl; while (!fi.empty()) { auto y = *fi.rbegin(); if (y.first >= x) { fi.erase(y); sti.pb({y, -1}); cnti--; sumi -= y.first; if (vx[l[y.second]] > x) { cnt1i++; sum1i += vx[l[y.second]]; //cout << -x * cnt1i + sum1i << endl; f1i.insert({vx[l[y.second]], y.second}); sti.pb({{vx[l[y.second]], y.second}, 2}); } else { f2i.insert({vx[r[y.second]], y.second}); sti.pb({{vx[r[y.second]], y.second}, 3}); } } else { break; } } //cout << sz(f1i) << ' ' << x << endl; while (!f1i.empty()) { auto y = *f1i.begin(); //cout << y.first << ' ' << x << endl; if (y.first <= x) { f1i.erase(y); sti.pb({y, -2}); cnt1i--; sum1i -= y.first; //cout << -x * cnt1i + sum1i << endl; f2i.insert({vx[r[y.second]], y.second}); sti.pb({{vx[r[y.second]], y.second}, 3}); } else { break; } } while (!f2i.empty()) { auto y = *f2i.begin(); if (y.first < x) { f2i.erase(y); sti.pb({y, -3}); cnti++; sumi += y.first; } else { break; } } } bool was[MAXN]; void updj(int x) { while (!fj.empty()) { auto y = *fj.begin(); if (y.first <= x) { fj.erase(y); stj.pb({y, -1}); cntj--; sumj -= y.first; if (vx[r[y.second]] < x) { cnt1j++; sum1j += vx[r[y.second]]; //cout << r[y.second] << endl; //cout << cnt1j << ' ' << r[y.second] << ' ' << x << endl; } else { f1j.insert({vx[r[y.second]], y.second}); stj.pb({{vx[r[y.second]], y.second}, 2}); } } else { break; } } while (!f1j.empty()) { auto y = *f1j.begin(); if (y.first < x) { f1j.erase(y); stj.pb({y, -2}); cnt1j++; //cout << cnt1j << ' ' << y.first << ' ' << x << endl; sum1j += y.first; //cout << cnt1j << endl; } else { break; } } } long long geti(int x) { return 1LL * x * cnti - sumi -1LL * x * cnt1i + sum1i; } long long getj(int x) { return -1LL * x * cntj + sumj + 1LL *x * cnt1j - sum1j; } vector<int> fs; void recalc(int i, int j) { i = vx[i]; j = vx[j]; // cout << j << endl; //cout << st[ft].first << ' ' << vx[l[st[ft].second]] << endl; while (ft < sz(st) && (st[ft].first <= i + j || vx[l[st[ft].second]] <= i)) { //cout << i << ' ' << j << ' ' << vx[l[st[ft].second]] << endl; //if (vx[l[st[ft].second]] < j) { if (!was[st[ft].second]) { delj(st[ft].second); addi(st[ft].second); was[st[ft].second] = true; fs.pb(st[ft].second); } //} ft++; } updi(i); updj(j); //cout << sum1j << endl; //if (i == 2 && j == 5) { //cout << getj(5) << endl; // } } long long getres(int i, int j) { // cout << cnti + cntj + cnt1i + cnt1j << endl; // cout << -1LL * vx[i] * cnt1i + sum1i << endl; long long add = geti(vx[i]) + getj(vx[j]); return add; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); //read(FILENAME); cin >> k >> n; long long ans = 0; int uk = 0; for (int i = 0; i < n; i++) { char c, c1; int x, x1; cin >> c >> x >> c1 >> x1; if (c == c1) { ans += abs(x1 - x); continue; } if (x > x1) { swap(x, x1); } ans += x1 - x + 1; l[uk] = x; r[uk] = x1; uk++; } n = uk; for (int i = 0; i < n; i++) { vx.pb(l[i]); vx.pb(r[i]); } vx.pb(0); sort(all(vx)); vx.resize(distance(vx.begin(), unique(all(vx)))); for (int i = 0; i < n; i++) { l[i] = lower_bound(all(vx), l[i]) - vx.begin(); r[i] = lower_bound(all(vx), r[i]) - vx.begin(); } if (k == 1) { for (int i = 0; i < n; i++) { fb[l[i]].pb(i); fe[r[i]].pb(i); //cout << l[i] << ' ' << r[i] << endl; } long long sum = 0; int cnt = 0; for (int i = 0; i < sz(vx); i++) { for (auto x: fe[i]) { sum += vx[r[x]]; cnt++; } score[i] += 1LL * vx[i] * cnt - sum; } cnt = 0; sum = 0; long long add = 2e18; for (int i = sz(vx) - 1; i >= 0; i--) { for (auto x: fb[i]) { sum += vx[l[x]]; cnt++; } score[i] += -1LL * vx[i] * cnt + sum; chkmin(add, score[i]); } //cout << add << endl; cout << ans + 2 * add << '\n'; return 0; } uk = 0; ft = 0; long long add = 2e18; for (int i = 0; i < n; i++) { //x - r[i] <= l[i] - y //x + y <= l[i] + r[i] st.pb({vx[l[i]] + vx[r[i]], i}); //cout << vx[l[i]] + vx[r[i]] << endl; fb[l[i]].pb(i); } //l - x <= y - r //l + r <= x + y; sort(all(st)); for (int i = 0; i < n; i++) { where[st[i].second] = i; addj(i); } for (int i = 0; i < sz(vx); i++) { for (auto x: fb[i]) { if (!was[x]) { delj(x); addi(x); was[x] = true; } } chkmax(uk, i); recalc(i, uk); //cout << cnt1i << endl; sti.clear(); stj.clear(); fs.clear(); // cout << vx[i] << endl; while (uk + 1 < sz(vx)) { long long cur = getres(i, uk); //cout << sz(f1i) << endl; int ft1 = ft; long long si, sj, ci, cj; si = sumi; ci = cnti; sj = sumj; cj = cntj; long long s1i, s1j, c1i, c1j; s1i = sum1i; c1i = cnt1i; s1j = sum1j; c1j = cnt1j; uk++; //cout << sz(sti) << endl; recalc(i, uk); long long cur1 = getres(i, uk); //cout << cur << ' ' << cur1 << endl; if (cur1 <= cur) { sti.clear(); stj.clear(); fs.clear(); continue; } //cout << cur << ' ' << cur1 << endl; sumi = si; cnti = ci; cntj = cj; sumj = sj; sum1i = s1i; cnt1i = c1i; cnt1j = c1j; sum1j = s1j; //cout << sum1i - 1LL * vx[i] * cnt1i << ' ' << sum1i << ' ' << cnt1i << endl; ft = ft1; for (int k = sz(sti) - 1; k >= 0; k--) { auto x = sti[k].first; int t = sti[k].second; if (t == 1 || t == -1) { if (t == 1) { fi.erase(x); } else { fi.insert(x); } } else if (t == 2 || t == -2) { if (t == 2) { f1i.erase(x); } else { f1i.insert(x); } } else { if (t == 3) { f2i.erase(x); } else { f2i.insert(x); } } } //cout << sz(f1i) << endl; sti.clear(); for (int k = sz(stj) - 1; k >= 0; k--) { auto x = stj[k].first; int t = stj[k].second; if (t == 1 || t == -1) { if (t == 1) { fj.erase(x); } else { fj.insert(x); } } else { if (t == 2) { f1j.erase(x); } else { f1j.insert(x); } } } stj.clear(); for (auto y: fs) { was[y] = false; } fs.clear(); uk--; break; } //cout << sz(sti) << endl; // cout << getres(i, uk) << endl; // cout << vx[i] << ' ' << vx[uk] << endl; chkmin(add, getres(i, uk)); } //cout << add << endl; cout << ans + 2 * add << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...