Submission #414939

#	Time	Username	Problem	Language	Result	Execution time	Memory
414939		Pro_ktmr	Food Court (JOI21_foodcourt)	C++17	68 / 100	1048 ms	46548 KiB

foodcourt

#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3,unroll-loops")
using ll = long long;
using ull = unsigned long long;
constexpr ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) for(int (i)=0; (i)<int(n); (i)++)
#define repi(i, a, b) for(int (i)=(a); (i)<int(b); (i)++)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
template<class T> bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
constexpr int dy[4]={-1,0,1,0};
constexpr int dx[4]={0,-1,0,1};

template<typename T, typename U>
struct LazySegmentTree{
private:
    int n, N;
    vector<T> node;
    vector<U> lazy;
    function<T(T, T)> F;
    T E;
    function<T(T, U)> G;
    function<U(U, U)> H;
    U I;
public:
    void init(int _n, function<T(T, T)> f, T e, function<T(T, U)> g, function<U(U, U)> h, U i){
        F = f; E = e;
        G = g; H = h; I = i;
        n = _n; N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, E);
        lazy.assign(2*N-1, I);
    }
    void init(vector<T> v, function<T(T, T)> f, T e, function<T(T, U)> g, function<U(U, U)> h, U i){
        F = f; E = e;
        G = g; H = h; I = i;
        n = v.size(); N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, E);
        lazy.assign(2*N-1, I);
        for(int i=0; i<n; i++) node[N-1+i] = v[i];
        for(int i=N-2; i>=0; i--) node[i] = F(node[(i<<1)+1], node[(i<<1)+2]);
    }
    int length(){
        return N;
    }
    T operator [](int a){
        return query(a, a+1);
    }
    void eval(int k){
        node[k] = G(node[k], lazy[k]);
        if(k < N-1){
            lazy[(k<<1)+1] = H(lazy[(k<<1)+1], lazy[k]);
            lazy[(k<<1)+2] = H(lazy[(k<<1)+2], lazy[k]);
        }
        lazy[k] = I;
    }
    void apply(int a, int b, U x, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        eval(k);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy[k] = H(lazy[k], x);
            eval(k);
        }
        else{
            apply(a, b, H(I, x), (k<<1)+1, l, (l+r)>>1);
            apply(a, b, H(I, x), (k<<1)+2, (l+r)>>1, r);
            node[k] = F(node[(k<<1)+1], node[(k<<1)+2]);
        }
    }
    T query(int a, int b, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        if(b <= l || r <= a) return E;
        eval(k);
        if(a <= l && r <= b) return node[k];
        return F(query(a, b, (k<<1)+1, l, (l+r)>>1), query(a, b, (k<<1)+2, (l+r)>>1, r));
    }
    int find_right(function<bool(T)> g, int a){
        if(!g(E)) return -1;
        T t = E;
        return min(find_right(g, a, 0, 0, N, t), n);
    }
    int find_right(function<bool(T)> g, int a, int k, int l, int r, T &t){
        eval(k);
        if(r-l == 1){
            t = F(t, node[k]);
            return g(t) ? r : a;
        }
        int m = (l + r) >> 1;
        if(m <= a) return find_right(g, a, (k<<1)+2, m, r, t);
        if(a <= l && g(F(t, node[k]))){
            t = F(t, node[k]);
            return r;
        }
        int L = find_right(g, a, (k<<1)+1, l, m, t);
        if(L < m) return L;
        int R = find_right(g, a, (k<<1)+2, m, r, t);
        return max(L, R);
    }
    int find_left(function<bool(T)> g, int b){
        if(!g(E)) return n + 1;
        T t = E;
        return find_left(g, b, 0, 0, N, t);
    }
    int find_left(function<bool(T)> g, int b, int k, int l, int r, T &t){
        eval(k);
        if(r-l == 1){
            t = F(node[k], t);
            return g(t) ? l : b;
        }
        int m = (l + r) >> 1;
        if(b <= m) return find_left(g, b, (k<<1)+1, l, m, t);
        if(r <= b && g(F(node[k], t))){
            t = F(node[k], t);
            return l;
        }
        int R = find_left(g, b, (k<<1)+2, m, r, t);
        if(m < R) return R;
        int L = find_left(g, b, (k<<1)+1, l, m, t);
        return min(L, R);
    }
};
 
template<typename T>
struct SegmentTree{
private:
    int n, N;
    vector<T> node;
    function<T(T, T)> F;
    T E;
public:
    void init(int _n, function<T(T, T)> f, T e){
        F = f;
        E = e;
        n = _n;
        N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, e);
    }
    void init(vector<T> v, function<T(T, T)> f, T e){
        F = f;
        E = e;
        n = v.size();
        N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, e);
        for(int i=0; i<n; i++) node[N-1+i] = v[i];
        for(int i=N-2; i>=0; i--) node[i] = F(node[(i<<1)+1], node[(i<<1)+2]);
    }
    T& operator [](int a){
        return node[N-1+a];
    }
    void update(int a, T x){
        a += N-1;
        node[a] = x;
        while(a > 0){
            a = (a-1)>>1;
            node[a] = F(node[(a<<1)+1], node[(a<<1)+2]);
        }
    }
    T query(int a, int b, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        if(b <= l || r <= a) return E;
        if(a <= l && r <= b) return node[k];
        return F(query(a, b, (k<<1)+1, l, (l+r)>>1), query(a, b, (k<<1)+2, (l+r)>>1, r));
    }
    int find_right(function<bool(T)> g, int a){
        if(!g(E)) return -1;
        T t = E;
        return min(find_right(g, a, 0, 0, N, t), n);
    }
    int find_right(function<bool(T)> g, int a, int k, int l, int r, T &t){
        if(r-l == 1){
            t = F(t, node[k]);
            return g(t) ? r : a;
        }
        int m = (l + r) >> 1;
        if(m <= a) return find_right(g, a, (k<<1)+2, m, r, t);
        if(a <= l && g(F(t, node[k]))){
            t = F(t, node[k]);
            return r;
        }
        int L = find_right(g, a, (k<<1)+1, l, m, t);
        if(L < m) return L;
        int R = find_right(g, a, (k<<1)+2, m, r, t);
        return max(L, R);
    }
    int find_left(function<bool(T)> g, int b){
        if(!g(E)) return n + 1;
        T t = E;
        return find_left(g, b, 0, 0, N, t);
    }
    int find_left(function<bool(T)> g, int b, int k, int l, int r, T &t){
        if(r-l == 1){
            t = F(node[k], t);
            return g(t) ? l : b;
        }
        int m = (l + r) >> 1;
        if(b <= m) return find_left(g, b, (k<<1)+1, l, m, t);
        if(r <= b && g(F(node[k], t))){
            t = F(node[k], t);
            return l;
        }
        int R = find_left(g, b, (k<<1)+2, m, r, t);
        if(m < R) return R;
        int L = find_left(g, b, (k<<1)+1, l, m, t);
        return min(L, R);
    }
};
 
using pll = pair<ll,ll>;
 
int N, M, Q;
int T[250001], L[250001], R[250001], A[250001]; ll B[250001];
int ans[250001];
 
LazySegmentTree<ll,pll> len;
 
vector<pair<int,ll>> query[250001];
vector<int> calc[250001];
SegmentTree<ll> st;
 
signed main(){
    scanf("%d%d%d", &N, &M, &Q);
    rep(i, Q){
        scanf("%d", T+i);
        if(T[i] == 1){
            scanf("%d%d%d%lld", L+i, R+i, A+i, B+i);
            L[i]--;
        }
        if(T[i] == 2){
            scanf("%d%d%lld", L+i, R+i, B+i);
            L[i]--;
        }
        if(T[i] == 3){
            scanf("%d%lld", A+i, B+i);
            A[i]--;
        }
    }
 
    // delete T[i] = 2 by modifing T[i] = 3
    // calc the end of each line
    len.init(vector<ll>(N, 0), [](ll l, ll r){ return l + r; }, 0,
        [](ll m, pll f){ return max(m + f.first, f.second); }, [](pll o, pll n){ return make_pair(o.first + n.first, max(o.second + n.first, n.second)); }, {0,-1e18L});
    rep(i, Q){
        if(T[i] == 1){
            len.apply(L[i], R[i], {B[i],-1e18L});
        }
        if(T[i] == 2){
            len.apply(L[i], R[i], {-B[i],0});
        }
        if(T[i] == 3){
            B[i] = len[A[i]] - B[i];
        }
    }
 
    // see each line
    rep(i, Q){
        if(T[i] == 1){
            query[L[i]].pb({i, B[i]});
            query[R[i]].pb({i, 0});
        }
        if(T[i] == 3){
            calc[A[i]].pb(i);
        }
    }
    st.init(Q, [](ll a, ll b){ return a+b; }, 0);
    rep(i, N){
        for(auto [j, x]: query[i]) st.update(j, x);
        for(auto j: calc[i]){
            ans[j] = st.find_left([j](ll x){ return x <= B[j]; }, j) - 1;
        }
    }
 
    // output
    rep(i, Q){
        if(T[i] == 3){
            if(ans[i] == -1) printf("0\n");
            else printf("%d\n", A[ans[i]]);
        }
    }
}

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define _rep(i, n) for(int (i)=0; (i)<int(n); (i)++)
      |                            ^
foodcourt.cpp:14:43: note: in expansion of macro '_rep'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
foodcourt.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
foodcourt.cpp:235:5: note: in expansion of macro 'rep'
  235 |     rep(i, Q){
      |     ^~~
foodcourt.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define _rep(i, n) for(int (i)=0; (i)<int(n); (i)++)
      |                            ^
foodcourt.cpp:14:43: note: in expansion of macro '_rep'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
foodcourt.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
foodcourt.cpp:255:5: note: in expansion of macro 'rep'
  255 |     rep(i, Q){
      |     ^~~
foodcourt.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define _rep(i, n) for(int (i)=0; (i)<int(n); (i)++)
      |                            ^
foodcourt.cpp:14:43: note: in expansion of macro '_rep'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
foodcourt.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
foodcourt.cpp:268:5: note: in expansion of macro 'rep'
  268 |     rep(i, Q){
      |     ^~~
foodcourt.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define _rep(i, n) for(int (i)=0; (i)<int(n); (i)++)
      |                            ^
foodcourt.cpp:14:43: note: in expansion of macro '_rep'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
foodcourt.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
foodcourt.cpp:278:5: note: in expansion of macro 'rep'
  278 |     rep(i, N){
      |     ^~~
foodcourt.cpp:15:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define _rep(i, n) for(int (i)=0; (i)<int(n); (i)++)
      |                            ^
foodcourt.cpp:14:43: note: in expansion of macro '_rep'
   14 | #define _overload3(_1, _2, _3, name, ...) name
      |                                           ^~~~
foodcourt.cpp:17:18: note: in expansion of macro '_overload3'
   17 | #define rep(...) _overload3(__VA_ARGS__, repi, _rep)(__VA_ARGS__)
      |                  ^~~~~~~~~~
foodcourt.cpp:286:5: note: in expansion of macro 'rep'
  286 |     rep(i, Q){
      |     ^~~
foodcourt.cpp:234:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  234 |     scanf("%d%d%d", &N, &M, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:236:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  236 |         scanf("%d", T+i);
      |         ~~~~~^~~~~~~~~~~
foodcourt.cpp:238:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  238 |             scanf("%d%d%d%lld", L+i, R+i, A+i, B+i);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:242:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  242 |             scanf("%d%d%lld", L+i, R+i, B+i);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:246:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  246 |             scanf("%d%lld", A+i, B+i);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~

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