oj.uz

Submission #959036

# Submission time Handle Problem Language Result Execution time Memory
959036 2024-04-07T12:05:35 Z Spade1 Food Court (JOI21_foodcourt) C++14
7 / 100
 1000 ms 524288 KB 
#pragma once
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef vector<vi> vvi;

template<typename T> using pq = priority_queue<T>;
template<typename T> using pqg = priority_queue<T, vector<T>, greater<T>>;

#define rep0(a) for (int i = 0; i < a; ++i)
#define rep1(i, a) for (int i = 0; i < a; ++i)
#define rep2(i, a, b) for (int i = a; i <= b; ++i)
#define rep3(i, a, b, c) for (int i = a; i <= b; i+=c) 
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1, rep0)(__VA_ARGS__)
#define repd0(a) for (int i = a; i >= 1; --i)
#define repd1(i, a) for (int i = a; i >= 1; --i)
#define repd2(i, a, b) for (int i = b; i >= a; --i)
#define repd3(i, a, b, c) for (int i = b; i >= a; i-=c)
#define repd(...) overload4(__VA_ARGS__, repd3, repd2, repd1, repd0)(__VA_ARGS__)
#define trav(a, x) for (auto& a : x)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
#define ins insert

template<typename T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1e9 + 7;
const int INF = 0x3fffffff;
const ll LINF = 0x1fffffffffffffff;
const char nl = '\n';
const int MX = 3e5 + 3;

template<class T>
struct fenwick {
  int n;
  vector<T> t;
  fenwick (int n=0){init(n);}
  void init(int _n) {
    n=_n;
    t.assign(n+1, T{});
  }
  void update(int x, const T &v) {
    for(int i = x+1; i <= n; i+=i&-i) t[i] = t[i]+v;
  }
  void update(int l, int r, const T &v) {
    update(l, v); update(r+1, -v);
  }
  T query(int x) {
    T res{};
    for (int i = x+1; i > 0; i-=i&-i) res = res+t[i];
    return res;
  }
  T query(int l, int r) {
    return query(r) - query(l-1);
  }
  //find the first index that sums to >= k
  int find(const T &k) {
    int x = 0;
    T cur{};
    for (int i = 1<<(31-__builtin_clz(n)); i > 0; i>>=1)
      if (x+i <= n && cur+t[x+i] < k) x+=i, cur+=t[i];
    return x;
  }
};

vll _index(MX), ans(MX, -1); vector<tuple<int, ll, ll>> ord[MX];
fenwick<ll> cnt(MX);

void solve() {
  int n, m, q; cin >> n >> m >> q;
  rep (T, 1, q) {
    int t; cin >> t;
    if (t == 1) {
      ll l, r, c, k; cin >> l >> r >> c >> k;
      ord[l].pb({1, T, k}); ord[r+1].pb({1, T, -k});
      _index[T] = c;
    }
    if (t == 2) {
      ll l, r, k; cin >> l >> r >> k;
      rep(i, l, r) {
        ord[i].pb({2, T, k});
      }
    }
    if (t == 3) {
      ll a, b; cin >> a >> b;
      ord[a].pb({3, T, b});
    }
  }
  rep(i, 1, n) {
    ll d = 0;
    for(auto [op, T, k] : ord[i]) {
      if (op == 1) cnt.update(T, k);  
      if (op == 2) {
        d += min(cnt.query(T)-d, k);
      }
      if (op == 3) {
        ans[T] = 0;
        rep(i, 1, T) if (cnt.query(i) >= d+k) {ans[T] = _index[i]; break;}
      }
    }
  }
  trav(a, ans) if (a != -1) cout << a << nl;
}

int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  int t = 1;
//  cin >> t;
  while (t--) { solve(); }
  return 0;
}

Compilation message

foodcourt.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
foodcourt.cpp: In function 'void solve()':
foodcourt.cpp:114:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |     for(auto [op, T, k] : ord[i]) {
      |              ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22108 KB Output is correct
2 Correct 23 ms 31824 KB Output is correct
3 Correct 12 ms 22872 KB Output is correct
4 Correct 20 ms 27532 KB Output is correct
5 Correct 7 ms 14684 KB Output is correct
6 Correct 7 ms 14684 KB Output is correct
7 Correct 32 ms 42040 KB Output is correct
8 Correct 38 ms 38416 KB Output is correct
9 Correct 35 ms 42116 KB Output is correct
10 Correct 35 ms 36444 KB Output is correct
11 Correct 31 ms 39148 KB Output is correct
12 Correct 39 ms 40280 KB Output is correct
13 Correct 37 ms 51244 KB Output is correct
14 Correct 56 ms 58008 KB Output is correct
15 Correct 29 ms 38028 KB Output is correct
16 Correct 50 ms 58196 KB Output is correct
17 Correct 21 ms 28508 KB Output is correct
18 Correct 34 ms 35168 KB Output is correct
19 Correct 7 ms 15196 KB Output is correct
20 Correct 8 ms 15360 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22108 KB Output is correct
2 Correct 23 ms 31824 KB Output is correct
3 Correct 12 ms 22872 KB Output is correct
4 Correct 20 ms 27532 KB Output is correct
5 Correct 7 ms 14684 KB Output is correct
6 Correct 7 ms 14684 KB Output is correct
7 Correct 32 ms 42040 KB Output is correct
8 Correct 38 ms 38416 KB Output is correct
9 Correct 35 ms 42116 KB Output is correct
10 Correct 35 ms 36444 KB Output is correct
11 Correct 31 ms 39148 KB Output is correct
12 Correct 39 ms 40280 KB Output is correct
13 Correct 37 ms 51244 KB Output is correct
14 Correct 56 ms 58008 KB Output is correct
15 Correct 29 ms 38028 KB Output is correct
16 Correct 50 ms 58196 KB Output is correct
17 Correct 21 ms 28508 KB Output is correct
18 Correct 34 ms 35168 KB Output is correct
19 Correct 7 ms 15196 KB Output is correct
20 Correct 8 ms 15360 KB Output is correct
21 Correct 21 ms 30044 KB Output is correct
22 Correct 22 ms 31580 KB Output is correct
23 Correct 13 ms 21336 KB Output is correct
24 Correct 17 ms 24668 KB Output is correct
25 Correct 7 ms 14684 KB Output is correct
26 Correct 6 ms 14684 KB Output is correct
27 Correct 30 ms 36444 KB Output is correct
28 Correct 30 ms 41052 KB Output is correct
29 Correct 27 ms 35840 KB Output is correct
30 Correct 27 ms 35928 KB Output is correct
31 Correct 43 ms 42300 KB Output is correct
32 Correct 40 ms 42084 KB Output is correct
33 Correct 37 ms 50260 KB Output is correct
34 Correct 49 ms 58196 KB Output is correct
35 Correct 35 ms 47068 KB Output is correct
36 Correct 51 ms 58884 KB Output is correct
37 Correct 7 ms 14936 KB Output is correct
38 Correct 11 ms 15196 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 709 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 651 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22108 KB Output is correct
2 Correct 23 ms 31824 KB Output is correct
3 Correct 12 ms 22872 KB Output is correct
4 Correct 20 ms 27532 KB Output is correct
5 Correct 7 ms 14684 KB Output is correct
6 Correct 7 ms 14684 KB Output is correct
7 Correct 32 ms 42040 KB Output is correct
8 Correct 38 ms 38416 KB Output is correct
9 Correct 35 ms 42116 KB Output is correct
10 Correct 35 ms 36444 KB Output is correct
11 Correct 31 ms 39148 KB Output is correct
12 Correct 39 ms 40280 KB Output is correct
13 Correct 37 ms 51244 KB Output is correct
14 Correct 56 ms 58008 KB Output is correct
15 Correct 29 ms 38028 KB Output is correct
16 Correct 50 ms 58196 KB Output is correct
17 Correct 21 ms 28508 KB Output is correct
18 Correct 34 ms 35168 KB Output is correct
19 Correct 7 ms 15196 KB Output is correct
20 Correct 8 ms 15360 KB Output is correct
21 Runtime error 709 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 17244 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22108 KB Output is correct
2 Correct 23 ms 31824 KB Output is correct
3 Correct 12 ms 22872 KB Output is correct
4 Correct 20 ms 27532 KB Output is correct
5 Correct 7 ms 14684 KB Output is correct
6 Correct 7 ms 14684 KB Output is correct
7 Correct 32 ms 42040 KB Output is correct
8 Correct 38 ms 38416 KB Output is correct
9 Correct 35 ms 42116 KB Output is correct
10 Correct 35 ms 36444 KB Output is correct
11 Correct 31 ms 39148 KB Output is correct
12 Correct 39 ms 40280 KB Output is correct
13 Correct 37 ms 51244 KB Output is correct
14 Correct 56 ms 58008 KB Output is correct
15 Correct 29 ms 38028 KB Output is correct
16 Correct 50 ms 58196 KB Output is correct
17 Correct 21 ms 28508 KB Output is correct
18 Correct 34 ms 35168 KB Output is correct
19 Correct 7 ms 15196 KB Output is correct
20 Correct 8 ms 15360 KB Output is correct
21 Correct 21 ms 30044 KB Output is correct
22 Correct 22 ms 31580 KB Output is correct
23 Correct 13 ms 21336 KB Output is correct
24 Correct 17 ms 24668 KB Output is correct
25 Correct 7 ms 14684 KB Output is correct
26 Correct 6 ms 14684 KB Output is correct
27 Correct 30 ms 36444 KB Output is correct
28 Correct 30 ms 41052 KB Output is correct
29 Correct 27 ms 35840 KB Output is correct
30 Correct 27 ms 35928 KB Output is correct
31 Correct 43 ms 42300 KB Output is correct
32 Correct 40 ms 42084 KB Output is correct
33 Correct 37 ms 50260 KB Output is correct
34 Correct 49 ms 58196 KB Output is correct
35 Correct 35 ms 47068 KB Output is correct
36 Correct 51 ms 58884 KB Output is correct
37 Correct 7 ms 14936 KB Output is correct
38 Correct 11 ms 15196 KB Output is correct
39 Runtime error 709 ms 524288 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 22108 KB Output is correct
2 Correct 23 ms 31824 KB Output is correct
3 Correct 12 ms 22872 KB Output is correct
4 Correct 20 ms 27532 KB Output is correct
5 Correct 7 ms 14684 KB Output is correct
6 Correct 7 ms 14684 KB Output is correct
7 Correct 32 ms 42040 KB Output is correct
8 Correct 38 ms 38416 KB Output is correct
9 Correct 35 ms 42116 KB Output is correct
10 Correct 35 ms 36444 KB Output is correct
11 Correct 31 ms 39148 KB Output is correct
12 Correct 39 ms 40280 KB Output is correct
13 Correct 37 ms 51244 KB Output is correct
14 Correct 56 ms 58008 KB Output is correct
15 Correct 29 ms 38028 KB Output is correct
16 Correct 50 ms 58196 KB Output is correct
17 Correct 21 ms 28508 KB Output is correct
18 Correct 34 ms 35168 KB Output is correct
19 Correct 7 ms 15196 KB Output is correct
20 Correct 8 ms 15360 KB Output is correct
21 Correct 21 ms 30044 KB Output is correct
22 Correct 22 ms 31580 KB Output is correct
23 Correct 13 ms 21336 KB Output is correct
24 Correct 17 ms 24668 KB Output is correct
25 Correct 7 ms 14684 KB Output is correct
26 Correct 6 ms 14684 KB Output is correct
27 Correct 30 ms 36444 KB Output is correct
28 Correct 30 ms 41052 KB Output is correct
29 Correct 27 ms 35840 KB Output is correct
30 Correct 27 ms 35928 KB Output is correct
31 Correct 43 ms 42300 KB Output is correct
32 Correct 40 ms 42084 KB Output is correct
33 Correct 37 ms 50260 KB Output is correct
34 Correct 49 ms 58196 KB Output is correct
35 Correct 35 ms 47068 KB Output is correct
36 Correct 51 ms 58884 KB Output is correct
37 Correct 7 ms 14936 KB Output is correct
38 Correct 11 ms 15196 KB Output is correct
39 Runtime error 709 ms 524288 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -