Submission #503446

#	Time	Username	Problem	Language	Result	Execution time	Memory
503446		cig32	Food Court (JOI21_foodcourt)	C++17	21 / 100	674 ms	196648 KiB

foodcourt

#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
#define int long long
 
const int MAXN = 2.5e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
    int u = uniform_int_distribution<int>(x, y)(rng);
    return u;
}
int bm(int b, int p) { // bigmod
    if(p==0) return 1;
    int r = bm(b, p/2);
    if(p&1) return (((r*r) % MOD) * b) % MOD;
    return (r*r) % MOD;
}
int N, M, Q;
 
struct segtree_beats {
    bool cmp(long long x, long long y) { return x > y; }
    int stok;
    const long long extr = 2e18;
    struct node {
        long long max1, max2, maxc;
        long long min1, min2, minc;
        long long lazy, sum;
        long long l, r;
    };
    vector<node> a;
    void pushtag_max(int idx, long long val) {
        if(val >= a[idx].max1) return;
        a[idx].sum -= (a[idx].max1 - val) * a[idx].maxc;
        a[idx].max1 = val;
        if(a[idx].l == a[idx].r) {
            a[idx].min1 = val;
        }
        else {
            if(a[idx].min1 >= val) {
                a[idx].min1 = val;
                a[idx].min2 = extr;
                a[idx].minc = a[idx].r - a[idx].l + 1;
            }
            else if(a[idx].min2 > val && a[idx].min2 != extr) {
                a[idx].min2 = val;
            }
        }
    }
    void pushtag_min(int idx, long long val) {
        if(val <= a[idx].min1) return;
        a[idx].sum += (val - a[idx].min1) * a[idx].minc;
        a[idx].min1 = val;
        if(a[idx].l == a[idx].r) {
            a[idx].max1 = val;
        }
        else {
            if(a[idx].max1 <= val) {
                a[idx].max1 = val;
                a[idx].max2 = -extr;
                a[idx].maxc = a[idx].r - a[idx].l + 1;
            }
            else if(a[idx].max2 < val && a[idx].max2 != -extr) {
                a[idx].max2 = val;
            }
        }
    }
    void pushtag_add(int idx, long long val) {
        a[idx].max1 += val;
        if(a[idx].max2 != -extr) a[idx].max2 += val;
        a[idx].min1 += val;
        if(a[idx].min2 != extr) a[idx].min2 += val;
        a[idx].lazy += val;
        a[idx].sum += val * (a[idx].r - a[idx].l + 1);
    }
    void pushdown(int idx) {
        pushtag_add(2*idx+1, a[idx].lazy);
        pushtag_add(2*idx+2, a[idx].lazy);
        a[idx].lazy = 0;
        pushtag_max(2*idx+1, a[idx].max1);
        pushtag_max(2*idx+2, a[idx].max1);
        pushtag_min(2*idx+1, a[idx].min1);
        pushtag_min(2*idx+2, a[idx].min1);
    }
    void pushup(int idx) {
        long long max1, max2, maxc;
        long long min1, min2, minc;
        long long lazy, sum;
        long long l, r;
        a[idx].max1 = max(a[2*idx+1].max1, a[2*idx+2].max1);
        a[idx].max2 = (a[2*idx+1].max1 == a[2*idx+2].max1 ?
                       max(a[2*idx+1].max2, a[2*idx+2].max2) :
                       (a[2*idx+1].max1 < a[2*idx+2].max1 ?
                        max(a[2*idx+1].max1, a[2*idx+2].max2) : 
                        max(a[2*idx+1].max2, a[2*idx+2].max1)
                        ));
        a[idx].maxc = (a[2*idx+1].max1 == a[2*idx+2].max1 ? 
                       a[2*idx+1].maxc + a[2*idx+2].maxc :
                       (a[2*idx+1].max1 < a[2*idx+2].max1 ? 
                        a[2*idx+2].maxc :
                        a[2*idx+1].maxc)
                       );
        a[idx].min1 = min(a[2*idx+1].min1, a[2*idx+2].min1);
        a[idx].min2 = (a[2*idx+1].min1 == a[2*idx+2].min1 ?
                       min(a[2*idx+1].min2, a[2*idx+2].min2) :
                       (a[2*idx+1].min1 > a[2*idx+2].min1 ?
                        min(a[2*idx+1].min1, a[2*idx+2].min2) : 
                        min(a[2*idx+1].min2, a[2*idx+2].min1)
                        ));
        a[idx].minc = (a[2*idx+1].min1 == a[2*idx+2].min1 ? 
                       a[2*idx+1].minc + a[2*idx+2].minc :
                       (a[2*idx+1].min1 > a[2*idx+2].min1 ? 
                        a[2*idx+2].minc :
                        a[2*idx+1].minc)
                       );
        a[idx].sum = a[2*idx+1].sum + a[2*idx+2].sum;
    }
    void init1(int l, int r, int idx, long long val) {
        a[idx].l = l, a[idx].r = r;
        if(l == r) {
            a[idx].max1 = a[idx].min1 = val;
            a[idx].max2 = -extr;
            a[idx].min2 = extr;
            a[idx].maxc = a[idx].minc = 1;
            a[idx].lazy = 0;
            a[idx].sum = val;
            return;
        }
        int mid = (l+r) >> 1;
        init1(l, mid, 2*idx+1, val);
        init1(mid+1, r, 2*idx+2, val);
        pushup(idx);
    }
    void u1(int l, int r, int constl, int constr, int idx, long long v) {
        if(v >= a[idx].max1) return;
        if(l<=constl && constr<=r && v>a[idx].max2) {
            pushtag_max(idx, v);
            return;
        }
        pushdown(idx);
        int mid = (constl+constr) >> 1;
        if(mid < l || r < constl) u1(l, r, mid+1, constr, 2*idx+2, v);
        else if(constr < l || r < mid+1) u1(l, r, constl, mid, 2*idx+1, v);
        else {
            u1(l, r, constl, mid, 2*idx+1, v);
            u1(l, r, mid+1, constr, 2*idx+2, v);
        }
        pushup(idx);
    }
    void u2(int l, int r, int constl, int constr, int idx, long long v) {
        if(v <= a[idx].min1) return;
        if(l<=constl && constr<=r && v<a[idx].min2) {
            pushtag_min(idx, v);
            return;
        }
        pushdown(idx);
        int mid = (constl+constr) >> 1;
        if(mid < l || r < constl) u2(l, r, mid+1, constr, 2*idx+2, v);
        else if(constr < l || r < mid+1) u2(l, r, constl, mid, 2*idx+1, v);
        else {
            u2(l, r, constl, mid, 2*idx+1, v);
            u2(l, r, mid+1, constr, 2*idx+2, v);
        }
        pushup(idx);
    }
    void u3(int l, int r, int constl, int constr, int idx, long long v) {
        if(l <= constl && constr <= r) {
            pushtag_add(idx, v);
            return;
        }
        pushdown(idx);
        int mid = (constl+constr) >> 1;
        if(mid < l || r < constl) u3(l, r, mid+1, constr, 2*idx+2, v);
        else if(constr < l || r < mid+1) u3(l, r, constl, mid, 2*idx+1, v);
        else {
            u3(l, r, constl, mid, 2*idx+1, v);
            u3(l, r, mid+1, constr, 2*idx+2, v);
        }
        pushup(idx);
    }
    long long qu(int l, int r, int constl, int constr, int idx) {
        if(l <= constl && constr <= r) {
            return a[idx].sum;
        }
        pushdown(idx);
        int mid = (constl+constr) >> 1;
        if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
        else if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
        else {
            return qu(l, r, constl, mid, 2*idx+1) + qu(l, r, mid+1, constr, 2*idx+2);
        }
    }
    public:
    void resize(int k) {
        stok = k;
        a.resize(4*k + 10);
    }
    void init(long long v) { // Initialize everything to v
        init1(0, stok, 0, v);
    }
    void min_with(int l, int r, long long v) {
        u1(l, r, 0, stok, 0, v);
    }
    void max_with(int l, int r, long long v) {
        u2(l, r, 0, stok, 0, v);
    }
    void range_add(int l, int r, long long v) {
        u3(l, r, 0, stok, 0, v);
    }
    long long query_sum(int l, int r) {
        return (long long)qu(l, r, 0, stok, 0);
    }
};
struct _1m {
    segtree_beats a;
    public:
    void join(int l, int r, int c, int k) {
        a.range_add(l, r, k);
    }
    void leave(int l, int r, int k) {
        a.range_add(l, r, -k);
        a.max_with(l, r, 0);
    }
    int service(int shop, int b) {
        return (a.query_sum(shop, shop) >= b ? 1 : 0);
    }
};
 
void solve_1m() {
    _1m ar;
    ar.a.resize(N);
    ar.a.init(0);
    while(Q--) {
        int t;
        cin >> t;
        if(t == 1) {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            ar.join(l, r, c, k);
        }
        else if(t == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            ar.leave(l, r, k);
        }
        else {
            int a, b;
            cin >> a >> b;
            cout << ar.service(a, b) << "\n";
        }
    }
}
segtree_beats stb;
vector<pair<int, pair<int, int> > > v[4*MAXN];
vector<int> w[4*MAXN];
vector<int> sq[4*MAXN];
int p[4*MAXN];
int ti=0;
int rp[MAXN];
int block;
void update(int l, int r, int constl, int constr, int idx, int c, int k) {
    if(l<=constl && constr<=r) {
        v[idx].push_back({ti, {c, k}});
        w[idx].push_back(w[idx].empty() ? k : w[idx][w[idx].size() - 1] + k);
        if(ti % block == block - 1) sq[idx].push_back(w[idx].size() - 1); // Last index
        return;
    }
    int mid = (constl+constr) >> 1;
    if(mid < l || r < constl) update(l, r, mid+1, constr, 2*idx+2, c, k);
    else if(constr < l || r < mid+1) update(l, r, constl, mid, 2*idx+1, c, k);
    else {
        update(l, r, constl, mid, 2*idx+1, c, k);
        update(l, r, mid+1, constr, 2*idx+2, c, k);
    }
} 
void build(int l, int r, int idx) {
    if(l == r) {
        rp[l] = idx;
        return;
    }
    int mid = (l+r) >> 1;
    build(l, mid, 2*idx+1);
    build(mid+1, r, 2*idx+2);
    p[2*idx+1] = p[2*idx+2] = idx;
}
void join(int l, int r, int c, int k) {
    ti++;
    stb.range_add(l, r, k);
    update(l, r, 0, MAXN-1, 0, c, k);
}
void leave(int l, int r, int k) {
    stb.range_add(l, r, -k);
    stb.max_with(l, r, 0);
}
int service(int a, int b) { // log^3 n
    int cur = rp[a];
    vector<int> q;
    int sum = 0;
    while(1) {
        q.push_back(cur);
        if(w[cur].size()) sum += w[cur][w[cur].size() - 1];
        if(cur == 0) break;
        cur = p[cur];
    }
    b += sum - stb.query_sum(a, a);
    if(b > sum) return 0;
    int lb = 0, rb = ti;
    while(lb < rb) { // log n
        int mid = (lb+rb) >> 1;
        int tot = 0;
        int cur = mid / block;
        for(int x: q) { // log n 
            if(w[x].empty()) continue;
            int lb2 = (cur > 0 && sq[x].size() > cur-1 ? sq[x][cur - 1] : 0);
            int rb2 = (sq[x].size() <= cur ? (int)w[x].size() - 1 : sq[x][cur]);
            while(lb2 < rb2) { // log n
                int mid2 = (lb2 + rb2 + 1) >> 1;
                if(v[x][mid2].first <= mid) {
                    lb2 = mid2;
                }
                else {
                    rb2 = mid2 - 1;
                }
            }
            if(v[x][lb2].first <= mid) {
                tot += w[x][lb2];
            }
        }
        if(tot >= b) rb = mid;
        else lb = mid + 1;
    }
    for(int x: q) {
        if(w[x].empty()) continue;
        int lb2 = 0, rb2 = w[x].size() - 1;
        while(lb2 < rb2) { // log n
            int mid2 = (lb2 + rb2 + 1) >> 1;
            if(v[x][mid2].first <= lb) {
                lb2 = mid2;
            }
            else {
                rb2 = mid2 - 1;
            }
        }
        if(v[x][lb2].first == lb) {
            return v[x][lb2].second.first;
        }
    }
}
 
void solve(int tc) {
    cin >> N >> M >> Q;
    block = max(3.0, ceil(sqrt(Q)));
    if(M == 1) { // Subtask 4
        solve_1m();
        return;
    }
    stb.resize(N);
    stb.init(0);
    build(0, MAXN-1, 0);
    while(Q--) {
        int t;
        cin >> t;
        if(t == 1) {
            int l, r, c, k;
            cin >> l >> r >> c >> k;
            join(l, r, c, k);
        }
        else if(t == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            leave(l, r, k);
        }
        else {
            int a, b;
            cin >> a >> b;
            cout << service(a, b) << "\n";
        }
    }
}
int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1; //cin >> t;
    for(int i=1; i<=t; i++) {
        solve(i);
    }
}

Compilation message (stderr)

foodcourt.cpp: In member function 'void segtree_beats::pushup(long long int)':
foodcourt.cpp:86:19: warning: unused variable 'max1' [-Wunused-variable]
   86 |         long long max1, max2, maxc;
      |                   ^~~~
foodcourt.cpp:86:25: warning: unused variable 'max2' [-Wunused-variable]
   86 |         long long max1, max2, maxc;
      |                         ^~~~
foodcourt.cpp:86:31: warning: unused variable 'maxc' [-Wunused-variable]
   86 |         long long max1, max2, maxc;
      |                               ^~~~
foodcourt.cpp:87:19: warning: unused variable 'min1' [-Wunused-variable]
   87 |         long long min1, min2, minc;
      |                   ^~~~
foodcourt.cpp:87:25: warning: unused variable 'min2' [-Wunused-variable]
   87 |         long long min1, min2, minc;
      |                         ^~~~
foodcourt.cpp:87:31: warning: unused variable 'minc' [-Wunused-variable]
   87 |         long long min1, min2, minc;
      |                               ^~~~
foodcourt.cpp:88:19: warning: unused variable 'lazy' [-Wunused-variable]
   88 |         long long lazy, sum;
      |                   ^~~~
foodcourt.cpp:88:25: warning: unused variable 'sum' [-Wunused-variable]
   88 |         long long lazy, sum;
      |                         ^~~
foodcourt.cpp:89:19: warning: unused variable 'l' [-Wunused-variable]
   89 |         long long l, r;
      |                   ^
foodcourt.cpp:89:22: warning: unused variable 'r' [-Wunused-variable]
   89 |         long long l, r;
      |                      ^
foodcourt.cpp: In function 'long long int service(long long int, long long int)':
foodcourt.cpp:314:48: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  314 |             int lb2 = (cur > 0 && sq[x].size() > cur-1 ? sq[x][cur - 1] : 0);
      |                                   ~~~~~~~~~~~~~^~~~~~~
foodcourt.cpp:315:37: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  315 |             int rb2 = (sq[x].size() <= cur ? (int)w[x].size() - 1 : sq[x][cur]);
      |                        ~~~~~~~~~~~~~^~~~~~
foodcourt.cpp:297:17: warning: control reaches end of non-void function [-Wreturn-type]
  297 |     vector<int> q;
      |                 ^

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 21 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11