oj.uz

Submission #1025038

# Submission time Handle Problem Language Result Execution time Memory
1025038 2024-07-16T14:32:19 Z hqminhuwu Pyramid Base (IOI08_pyramid_base) C++14
100 / 100
 1010 ms 262144 KB 
#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 * 4], lazy[N * 4], 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 = (i == len);
           // 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();
                //cout << "add " << t.nd.st << " " << t.nd.nd << " " << v << " " << u << " " << t.st << "\n";
                update(1, 1, m, t.nd.st, min(m, (ll)t.nd.nd + len - 1), 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, m, t.nd.st, min(m, (ll)t.nd.nd + len - 1), -t.st);
                }
            }
            if (i >= len && flag){
 
                res = min (res, get(1, 1, m, len, m));
                //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(33541) << "\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{
    struct node{
        int val, mx, pre, suf, len;
        node(){}
        node(ll x) : val(x), mx(1), pre(1), suf(1), len(1){}
    };
    
    node comb (node u, node v){
        node res;
        if (u.val == v.val){
            res.val = u.val;
            res.pre = u.pre;
            res.suf = v.suf;
            if (u.suf == u.len) res.pre += v.pre;
            if (v.pre == v.len) res.suf += u.suf;
            res.mx = max (u.suf + v.pre, max(u.mx, v.mx));
            res.len = u.len + v.len;
        } else 
        if (u.val < v.val){
            res.val = u.val;
            res.pre = u.pre;
            res.suf = 0;
            res.mx = u.mx;
            res.len = u.len + v.len;
        } else {
            res.val = v.val;
            res.suf = v.suf;
            res.pre = 0;
            res.mx = v.mx;
            res.len = u.len + v.len;
        }
        return res;
    }
    
    node tree[N << 2];
    int lazy[N << 2];
    
    void down (int i){
        if (lazy[i] == 0)
            return;
        lazy[(i << 1)] += lazy[i];
        lazy[(i << 1) | 1] += lazy[i];
        tree[(i << 1)].val += lazy[i];
        tree[(i << 1) | 1].val += lazy[i];
        lazy[i] = 0;
    }
    
    void build (int i, int l, int r){
        if (l == r){
            tree[i] = node(0);
            return;
        }
        int mid = (l + r) >> 1;
        build(i << 1, l, mid);
        build(i << 1 | 1, mid + 1, r);
        tree[i] = comb(tree[i << 1], tree[i << 1 | 1]);
    }
    
    void update (int i, int l, int r, int u, int v, ll val){
        if (l > v || r < u)
            return;
        if (l >= u && r <= v){
            tree[i].val += 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] = comb (tree[(i << 1)], tree[(i << 1) | 1]);
    }
 
    vector <pii> add[2 * N], rem[2 * N];
    int f[N];
 
    void solve(){
        forr (i, 1, p){
            int x, y, u, v, w;
            cin >> x >> y >> u >> v >> w;
            add[x].pb({y, v});
            rem[u].pb({y, v});
        }
        f[0] = 0;
        build(1, 1, m);
        int res = 0;
        forr (i, 1, n){
            for (pii t : rem[i - 1]){
                update(1, 1, m, t.st, t.nd, -1);
            }
            f[i] = f[i - 1];
            while (f[i] < i || (f[i] <= n && tree[1].val == 0 && tree[1].mx >= f[i] - i + 1)){
                res = max (res, f[i] - i + 1);
                f[i]++;
                for (pii t : add[f[i]]){
                    update(1, 1, m, t.st, t.nd, 1);
                }
            }
            //cout << i << " " << f[i] << "\n";
        }
        cout << res << "\n";
    }
}
 
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;
    if (b > 0) sub2::solve();
    else sub3::solve();
 
    return 0;
}
/*
 
 
 
*/

Compilation message

pyramid_base.cpp: In function 'int sub2::calc(int)':
pyramid_base.cpp:93:21: warning: unused variable 'u' [-Wunused-variable]
   93 |                 int u = upper_bound(all(co), t.nd.nd + len - 1) - co.begin();
      |                     ^
pyramid_base.cpp:94:21: warning: unused variable 'v' [-Wunused-variable]
   94 |                 int v = lower_bound(all(co), t.nd.st) - co.begin();
      |                     ^
pyramid_base.cpp:101:25: warning: unused variable 'u' [-Wunused-variable]
  101 |                     int u = upper_bound(all(co), t.nd.nd + len - 1) - co.begin();
      |                         ^
pyramid_base.cpp:102:25: warning: unused variable 'v' [-Wunused-variable]
  102 |                     int v = lower_bound(all(co), t.nd.st) - co.begin() + 1;
      |                         ^
pyramid_base.cpp:86:13: warning: unused variable 'z' [-Wunused-variable]
   86 |         int z = upper_bound(all(co), len) - co.begin();
      |             ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 188328 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 188244 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 188380 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 189012 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 194956 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 238160 KB Output is correct
2 Correct 108 ms 238928 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 235860 KB Output is correct
2 Correct 111 ms 238376 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 219988 KB Output is correct
2 Correct 157 ms 219984 KB Output is correct
3 Correct 135 ms 219912 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 220988 KB Output is correct
2 Correct 451 ms 221016 KB Output is correct
3 Correct 296 ms 220760 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 494 ms 221392 KB Output is correct
2 Correct 161 ms 221412 KB Output is correct
3 Correct 176 ms 220872 KB Output is correct
4 Correct 667 ms 221648 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 221904 KB Output is correct
2 Correct 699 ms 221788 KB Output is correct
3 Correct 430 ms 222160 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 222416 KB Output is correct
2 Correct 923 ms 222416 KB Output is correct
3 Correct 962 ms 222412 KB Output is correct
4 Correct 952 ms 222396 KB Output is correct
5 Correct 916 ms 222284 KB Output is correct
6 Correct 417 ms 222436 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 556 ms 258580 KB Output is correct
2 Correct 301 ms 209236 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 262144 KB Output is correct
2 Correct 689 ms 262144 KB Output is correct
3 Correct 442 ms 251928 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 796 ms 262144 KB Output is correct
2 Correct 1010 ms 262144 KB Output is correct
3 Correct 1010 ms 262144 KB Output is correct
4 Correct 917 ms 262144 KB Output is correct
5 Correct 627 ms 262144 KB Output is correct