Submission #494685

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
494685	2021-12-16T02:01:20 Z	blue	Food Court (JOI21_foodcourt)	C++17	Compilation error	0 ms	0 KB

foodcourt

#include <iostream>
#include <vector>
using namespace std;
 
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
 
const int mx = 250'000;
const ll INF = 1'000'000'000'000'000'000LL;
 
vi L(1+mx), R(1+mx), C(1+mx), A(1+mx);
vll K(1+mx), B(1+mx);
vi T(1+mx);
 
vi st[1+mx], en[1+mx], qr[1+mx];
 
vi ans(1+mx, 0);
 
void build(segtree* t, int L, int R, segtree* par);
 
struct segtree
{
    int l;
    int r;
 
    pair<ll, int> mn;
    pair<ll, int> mx;
    ll lp = 0;
 
    segtree* left = NULL;
    segtree* right = NULL;
    segtree* parent = NULL;
 
 
    segtree()
    {
        ;
    }
  
    segtree(int L, int R, segtree* par)
    {
      build(this, L, R, par);
	}
 
    void add(int L, int R, ll V)
    {
        if(r < L || R < l) return;
        else if(L <= l && r <= R)
        {
            lp += V;
            mn.first += V;
            mx.first += V;
        }
        else
        {
            left->add(L, R, V);
            right->add(L, R, V);
 
            mn = min(left->mn, right->mn);
            mn.first += lp;
 
            mx = max(left->mx, right->mx);
            mx.first += lp;
        }
    }
 
    pair<ll, int> rangemin(int L, int R)
    {
        if(R < l || r < L) return {INF, -1};
        else if(L <= l && r <= R) return mn;
        else
        {
            auto res = min(left->rangemin(L, R), right->rangemin(L, R));
            res.first += lp;
            return res;
        }
    }
};

segtree st1[530'001];

void build(segtree* t, int L, int R, segtree* par)
{
  t->l = L;
        t->r = R;
        t->parent = par;
        t->mn = {0, l};
        t->mx = {0, l};
        if(t->l == t->r) return;
        int m = (t->l+t->r)/2;
      t->left = st1[++ct];
      t->right = st1[++ct];
        build(t->left, t->l, m, t);
        build(t->right, m+1, t->r, t);
}
 
int locate(segtree& S, int L, ll V) //find the first position > L with a value >= V, or return -1 if it doesn't exist
{
    segtree* pos = &S;
    ll above_lp = 0;
    while(!(pos->l == L && pos->r == L))
    {
        above_lp += pos->lp;
        if(L <= (pos->l + pos->r)/2)
            pos = pos->left;
        else
            pos = pos->right;
    }
 
    while(1)
    {
        if(pos->parent == NULL) return -1;
 
        if(above_lp + pos->parent->right->mx.first >= V)
        {
            pos = pos->parent->right;
            break;
        }
        pos = pos->parent;
        above_lp -= pos->lp;
    }
 
    while(!(pos->l == pos->r))
    {
        above_lp += pos->lp;
        if(above_lp + pos->left->mx.first >= V)
            pos = pos->left;
        else
            pos = pos->right;
    }
 
    return pos->l;
}
 
struct BIT
{
    int Z;
    vll arr;
 
    BIT()
    {
        ;
    }
 
    BIT(int z)
    {
        Z = z;
        arr = vll(1+z, 0);
    }
 
    void add(int i, ll v)
    {
        for(int j = i; j <= Z; j += j&-j)
            arr[j] += v;
    }
 
    ll prefsum(int i)
    {
        ll ans = 0;
        for(int j = i; j >= 1; j -= j&-j)
            ans += arr[j];
        return ans;
    }
};
 
 
 
int main()
{
  	ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
    int N, M, Q;
    cin >> N >> M >> Q;
 
    for(int j = 1; j <= Q; j++)
    {
        cin >> T[j];
        if(T[j] == 1) cin >> L[j] >> R[j] >> C[j] >> K[j];
        else if(T[j] == 2)
        {
            cin >> L[j] >> R[j] >> K[j];
            K[j] *= -1;
        }
        else cin >> A[j] >> B[j];
 
        if(T[j] <= 2)
        {
            st[L[j]].push_back(j);
            en[R[j]].push_back(j);
        }
        else qr[A[j]].push_back(j);
    }
 
    vll S(1+Q, 0);
 
    vi ans(1+Q, 0);
 
    segtree ST(0, Q, NULL);
    segtree ST_plus(0, Q, NULL);
    BIT plus_sum(1+Q), minus_sum(1+Q);
 
    for(int i = 1; i <= N; i++)
    {
        for(int o: st[i])
        {
            S[o] = K[o];
            ST.add(o, Q, +K[o]);
            if(K[o] < 0) minus_sum.add(o, -K[o]);
 
            if(K[o] > 0) ST_plus.add(o, Q, +K[o]);
        }
 
        for(int q: qr[i])
        {
            int p = ST.rangemin(0, q-1).second;
 
            ll min_sum = minus_sum.prefsum(q) - minus_sum.prefsum(p);
 
            // cerr << "p = " << p << '\n';
            // cerr << "total loss = " << minus_sum << '\n';
 
            ll plus_sub = ST_plus.rangemin(p, p).first;
 
            int lo = locate(ST_plus, p, min_sum + B[q] + plus_sub);
            if(lo != -1 && lo <= q)
            {
                ans[q] = C[lo];
            }
        }
 
        for(int o: en[i])
        {
            S[o] = 0;
            ST.add(o, Q, -K[o]);
            if(K[o] < 0) minus_sum.add(o, +K[o]);
 
            if(K[o] > 0)
                ST_plus.add(o, Q, -K[o]);
        }
    }
 
    for(int q = 1; q <= Q; q++)
        if(T[q] == 3)
            cout << ans[q] << '\n';
    // cout << '\n';
}

Compilation message

foodcourt.cpp:20:6: error: variable or field 'build' declared void
   20 | void build(segtree* t, int L, int R, segtree* par);
      |      ^~~~~
foodcourt.cpp:20:12: error: 'segtree' was not declared in this scope
   20 | void build(segtree* t, int L, int R, segtree* par);
      |            ^~~~~~~
foodcourt.cpp:20:21: error: 't' was not declared in this scope; did you mean 'st'?
   20 | void build(segtree* t, int L, int R, segtree* par);
      |                     ^
      |                     st
foodcourt.cpp:20:24: error: expected primary-expression before 'int'
   20 | void build(segtree* t, int L, int R, segtree* par);
      |                        ^~~
foodcourt.cpp:20:31: error: expected primary-expression before 'int'
   20 | void build(segtree* t, int L, int R, segtree* par);
      |                               ^~~
foodcourt.cpp:20:38: error: 'segtree' was not declared in this scope
   20 | void build(segtree* t, int L, int R, segtree* par);
      |                                      ^~~~~~~
foodcourt.cpp:20:47: error: 'par' was not declared in this scope
   20 | void build(segtree* t, int L, int R, segtree* par);
      |                                               ^~~
foodcourt.cpp: In constructor 'segtree::segtree(int, int, segtree*)':
foodcourt.cpp:43:7: error: 'build' was not declared in this scope
   43 |       build(this, L, R, par);
      |       ^~~~~
foodcourt.cpp: In function 'void build(segtree*, int, int, segtree*)':
foodcourt.cpp:88:21: error: 'l' was not declared in this scope
   88 |         t->mn = {0, l};
      |                     ^
foodcourt.cpp:88:22: error: no match for 'operator=' (operand types are 'std::pair<long long int, int>' and '<brace-enclosed initializer list>')
   88 |         t->mn = {0, l};
      |                      ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = long long int; _T2 = int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<long long int, int>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<long long int, int>&, const std::__nonesuch&>::type' {aka 'const std::pair<long long int, int>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = long long int; _T2 = int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<long long int, int>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<long long int, int>&&, std::__nonesuch&&>::type' {aka 'std::pair<long long int, int>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = int]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
foodcourt.cpp:88:22: note:   couldn't deduce template parameter '_U1'
   88 |         t->mn = {0, l};
      |                      ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = int]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
foodcourt.cpp:88:22: note:   couldn't deduce template parameter '_U1'
   88 |         t->mn = {0, l};
      |                      ^
foodcourt.cpp:89:22: error: no match for 'operator=' (operand types are 'std::pair<long long int, int>' and '<brace-enclosed initializer list>')
   89 |         t->mx = {0, l};
      |                      ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:390:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type) [with _T1 = long long int; _T2 = int; typename std::conditional<std::__and_<std::is_copy_assignable<_T1>, std::is_copy_assignable<_T2> >::value, const std::pair<_T1, _T2>&, const std::__nonesuch&>::type = const std::pair<long long int, int>&]'
  390 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:393:41: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, const std::pair<long long int, int>&, const std::__nonesuch&>::type' {aka 'const std::pair<long long int, int>&'}
  390 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~    
  391 |   __and_<is_copy_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~        
  392 |          is_copy_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  393 |   const pair&, const __nonesuch&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:401:7: note: candidate: 'std::pair<_T1, _T2>& std::pair<_T1, _T2>::operator=(typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type) [with _T1 = long long int; _T2 = int; typename std::conditional<std::__and_<std::is_move_assignable<_Tp>, std::is_move_assignable<_T2> >::value, std::pair<_T1, _T2>&&, std::__nonesuch&&>::type = std::pair<long long int, int>&&]'
  401 |       operator=(typename conditional<
      |       ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:404:31: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::conditional<true, std::pair<long long int, int>&&, std::__nonesuch&&>::type' {aka 'std::pair<long long int, int>&&'}
  401 |       operator=(typename conditional<
      |                 ~~~~~~~~~~~~~~~~~~~~~
  402 |   __and_<is_move_assignable<_T1>,
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  403 |          is_move_assignable<_T2>>::value,
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  404 |   pair&&, __nonesuch&&>::type __p)
      |   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, const _U1&>, std::is_assignable<_T2&, const _U2&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = int]'
  418 |  operator=(const pair<_U1, _U2>& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:418:2: note:   template argument deduction/substitution failed:
foodcourt.cpp:89:22: note:   couldn't deduce template parameter '_U1'
   89 |         t->mx = {0, l};
      |                      ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from foodcourt.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:430:2: note: candidate: 'template<class _U1, class _U2> typename std::enable_if<std::__and_<std::is_assignable<_T1&, _U1&&>, std::is_assignable<_T2&, _U2&&> >::value, std::pair<_T1, _T2>&>::type std::pair<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U1 = _U1; _U2 = _U2; _T1 = long long int; _T2 = int]'
  430 |  operator=(pair<_U1, _U2>&& __p)
      |  ^~~~~~~~
/usr/include/c++/10/bits/stl_pair.h:430:2: note:   template argument deduction/substitution failed:
foodcourt.cpp:89:22: note:   couldn't deduce template parameter '_U1'
   89 |         t->mx = {0, l};
      |                      ^
foodcourt.cpp:92:23: error: 'ct' was not declared in this scope; did you mean 't'?
   92 |       t->left = st1[++ct];
      |                       ^~
      |                       t