Submission #1024963

#TimeUsernameProblemLanguageResultExecution timeMemory
1024963hqminhuwuPyramid Base (IOI08_pyramid_base)C++14
22 / 100
530 ms262144 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair <ll,ll> pll; typedef pair <int,int> pii; typedef pair <int,pii> piii; #define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a) #define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);) #define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a) #define st first #define nd second #define pb push_back #define mp make_pair #define all(x) begin(x),end(x) #define mask(i) (1LL << (i)) #define bit(x, i) (((x) >> (i)) & 1) #define bp __builtin_popcountll #define file "test" template<class X, class Y> bool minz(X &x, const Y &y) { if (x > y) { x = y; return true; } return false; } template<class X, class Y> bool maxz(X &x, const Y &y) { if (x < y) { x = y; return true; } return false; } const int N = 1e6 + 5; const ll oo = (ll) 1e16; const ll mod = 1e9 + 7; // 998244353; ll n, m, b, p; namespace sub2{ int tree[N], lazy[N], sz; vector <piii> add[2 * N], rem[2 * N]; vector <int> co; void down (int i){ if (!lazy[i]) return; forr (j, i << 1, (i << 1) | 1){ //cout << i << " " << j << "\n"; tree[j] += lazy[i]; lazy[j] += lazy[i]; } lazy[i] = 0; } void update(int i, int l, int r, int u, int v, int val){ if (l > v || r < u) return; if (l >= u && r <= v){ //cout << i << " " << l << " " << r << " " << val << "\n"; tree[i] += val; lazy[i] += val; return; } down(i); int mid = (l + r) >> 1; update(i << 1, l, mid, u, v, val); update(i << 1 | 1, mid + 1, r, u, v, val); tree[i] = min(tree[i << 1], tree[i << 1 | 1]); //cout << i << " " << tree[i] << "\n"; } int get (int i, int l, int r, int u, int v){ if (u > r || v < l) return 2 * mod; if (l >= u && r <= v) return tree[i]; down(i); int mid = (l + r) >> 1; return min(get(i << 1, l, mid, u, v), get(i << 1 | 1, mid + 1, r, u, v)); } int calc(int len){ if (!len) return 0; memset (tree, 0, sizeof tree); memset (lazy, 0, sizeof lazy); int z = upper_bound(all(co), len) - co.begin(); int res = 2 * mod; forr (i, 1, n){ int flag = 0; // cout << i << ":\n"; for (piii t : add[i]){ flag = 1; int u = upper_bound(all(co), t.nd.nd + len - 1) - co.begin(); int v = lower_bound(all(co), t.nd.st) - co.begin() + 1; //cout << "add " << t.nd.st << " " << t.nd.nd << " " << v << " " << u << " " << t.st << "\n"; update(1, 1, sz, v, u, t.st); } if (i >= len){ for (piii t : rem[i - len]){ flag = 1; int u = upper_bound(all(co), t.nd.nd + len - 1) - co.begin(); int v = lower_bound(all(co), t.nd.st) - co.begin() + 1; //cout << "rem " << t.nd.st << " " << t.nd.nd << " " << v << " " << u << "\n"; update(1, 1, sz, v, u, -t.st); } } if (i >= len && flag){ res = min (res, get(1, 1, sz, z, sz)); //cout << tree[1] << "\n"; } } return res; } void solve(){ forr (i, 1, p){ int x, y, u, v, w; cin >> x >> y >> u >> v >> w; add[x].pb({w, {y, v}}); rem[u].pb({w, {y, v}}); co.pb(y); co.pb(v); } co.pb(m); sort(all(co)); co.erase(unique(all(co)), co.end()); sz = co.size(); //cout << sz << "\n"; // for (int u : co){ // cout << u << " "; // } // cout << "\n"; // cout << calc(4) << "\n"; int l = 0, r = min(n, m); while (l < r){ int mid = (l + r + 1) >> 1; if (calc(mid) <= b) l = mid; else r = mid - 1; } cout << l << "\n"; } } namespace sub3{ void solve(){ } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef hqm freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); #endif cin >> n >> m >> b >> p; sub2::solve(); 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...
#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...
#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...