Submission #240522

#TimeUsernameProblemLanguageResultExecution timeMemory
240522Aldas25Shortcut (IOI16_shortcut)C++14
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; #define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr) #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define REP(n) FOR(O, 1, (n)) #define f first #define s second #define pb push_back typedef long long ll; typedef pair<int, int> pii; typedef vector<ll> vl; typedef vector<int> vi; typedef vector<pii> vii; const int MAXN = 100100; const ll INF = 1e17; int n; ll c; ll l[MAXN]; ll d[MAXN]; ll x[MAXN]; vl xs; ll a[MAXN], b[MAXN]; vector<pair<ll, int>> srtB, srtA; int idToUpd[MAXN], idToGet[MAXN]; ll tree[4 * MAXN][4]; void build (int index, int id = 1, int le = 0, int ri = n - 1) { if (le == ri) { tree[id][index] = -INF; return; } int mid = (le + ri) / 2; build (index, 2 * id, le, mid); build (index, 2 * id + 1, mid + 1, ri); tree[index][id] = max(tree[index][2 * id], tree[index][2 * id + 1]); } void upd (int index, int p, ll kx, int id = 1, int le = 0, int ri = n - 1) { if (le == ri) { tree[id][index] = kx; return; } int mid = (le + ri) / 2; if (p <= mid) { upd(index, p, kx, 2 * id, le, mid); } else { upd(index, p, kx, 2 * id + 1, mid + 1, ri); } tree[id][index] = max(tree[2 * id][index], tree[2 * id + 1][index]); } ll get (int index, int kx, int y, int id = 1, int le = 0, int ri = n - 1) { if (kx > ri || y < le) { return 0ll; } if (kx <= le && ri <= y) { return tree[id][index]; } int mid = (le + ri) / 2; return max(get(index, kx, y, 2 * id, le, mid), get(index, kx, y, 2 * id + 1, mid + 1, ri)); } bool doesExist (ll mn1, ll mx1, ll mn2, ll mx2) { /*FOR(y, 0, n-1) FOR(z, 0, n-1) { if (mn1 <= x[y]+x[z] && x[y]+x[z] <= mx1 && mn2 <= x[z]-x[y] && x[z]-x[y] <= mx2) return true; } return false;*/ FOR(z, 0, n - 1) { ll mnY = max(mn1 - x[z], x[z] - mx2); ll mxY = min(mx1 - x[z], x[z] - mn2); auto it = lower_bound(xs.begin(), xs.end(), mnY); if (it != xs.end()) { ll num = (*it); if (num <= mxY) { return true; } } } return false; } bool check (ll k) { //cout << "----------------------\nk = " << k << endl; ll mn1 = -INF, mn2 = -INF, mx1 = INF, mx2 = INF; //ll mnA = INF, mxA = -INF, mnB = INF, mxB = -INF; //FOR(i, 0, 3) build(i); FOR(i, 1, 2) build(i); //int rId = 0; FOR(i, 0, n - 1) { idToUpd[srtB[i].s] = i; //cout << " i=" << i << " srtB = " << srtB[i].f << " id=" << srtB[i].s << endl; // while (rId < n && srtA[rId].f - k <= srtB[i].s) { // idToGet[srtA[rId].s] = i-1; // rId++; // } } // int le = 0; FOR(j, 0, n - 1) { int kj = 0; int le = 0, ri = n - 1; while (le < ri) { int mid = (le + ri + 1) / 2; //cout << " " << srtB[mid].f << " " << a[j]-k << endl; if (srtB[mid].f < a[j] - k) { le = mid; } else { ri = mid - 1; } } //le = min(le, ri); if (a[j] - k <= srtB[le].f) { le--; } //cout << " j=" << j << " aj-k=" << a[j]-k << " le= " << le << endl; kj = le; //ll mnA = (-1ll)*(get(0, 0,kj)); ll mxA = (get(1, 0, kj)); ll mnB = (-1ll) * (get(2, 0, kj)); // ll mxB = (get(3, 0,kj)); //cout << " j=" << j if (mxA > 0) { mn1 = max(mn1, mxA + a[j] - (k - c)); //mn1 = max(mn1, mnA + a[j] - (k-c)); mx1 = min(mx1, mnB + b[j] + (k - c)); //mx1 = min(mx1, mxB + b[j] + (k-c)); mn2 = max(mn2, a[j] - mnB - (k - c)); //mn2 = max(mn2, a[j] - mxB - (k-c)); mx2 = min(mx2, b[j] - mxA + (k - c)); //mx2 = min(mx2, b[j] - mnA + (k-c)); } kj = idToUpd[j]; // upd(0, kj, (-a[j])); upd(1, kj, (a[j])); upd(2, kj, (-b[j])); // upd(3, kj, (b[j])); } return doesExist(mn1, mx1, mn2, mx2); } ll solve () { x[0] = 0; FOR(i, 1, n - 1) x[i] = x[i - 1] + l[i - 1]; FOR(i, 0, n - 1) xs.pb(x[i]); FOR(i, 0, n - 1) a[i] = x[i] + d[i]; FOR(i, 0, n - 1) b[i] = x[i] - d[i]; FOR(i, 0, n - 1) srtA.pb({a[i], i}); FOR(i, 0, n - 1) srtB.pb({b[i], i}); sort(srtA.begin(), srtA.end()); sort(srtB.begin(), srtB.end()); ll le = 0, ri = 2 * (1e14); while (le < ri) { ll mid = (le + ri) / 2; if (check(mid)) { ri = mid; } else { le = mid + 1; } } return le; } long long find_shortcut(int _n,vector<int> _l,vector<int> _d,int _c) { n = _n; c = _c; FOR(i, 0, n-2) l[i] = (el); FOR(i, 0, n-1) d[i] = (el); return solve(); } /*inline int read() { int x=0,f=1;char ch=getchar(); //while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; }*/ /*int main() { //FAST_IO; //cin >> n >> c; //FOR(i, 0, n - 2) cin >> l[i]; //FOR(i, 0, n - 1) cin >> d[i];* n = read(); c = read(); FOR(i, 0, n-2) l[i] = read(); FOR(i, 0, n-1) d[i] = read(); cout << solve() << "\n"; return 0; }*/ /* 4 10 10 20 20 0 40 0 30 ans: 80 9 30 10 10 10 10 10 10 10 10 20 0 30 0 0 40 0 40 0 ans: 110 4 1 2 2 2 1 10 10 1 ans: 21 3 3 1 1 1 1 1 ans: 4 */

Compilation message (stderr)

shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:213:28: error: 'el' was not declared in this scope
     FOR(i, 0, n-2) l[i] = (el);
                            ^~
shortcut.cpp:213:28: note: suggested alternative: '_l'
     FOR(i, 0, n-2) l[i] = (el);
                            ^~
                            _l
shortcut.cpp:214:28: error: 'el' was not declared in this scope
     FOR(i, 0, n-1) d[i] = (el);
                            ^~
shortcut.cpp:214:28: note: suggested alternative: '_l'
     FOR(i, 0, n-1) d[i] = (el);
                            ^~
                            _l