oj.uz

Submission #959049

# Submission time Handle Problem Language Result Execution time Memory
959049 2024-04-07T12:23:09 Z Spade1 Food Court (JOI21_foodcourt) C++14
20 / 100
 718 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[x];
    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) {
        int idx = cnt.find(d+k);
        ans[T] = (idx > T ? 0 : _index[idx]);
      }
    }
  }
  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 11 ms 22108 KB Output is correct
2 Correct 21 ms 31892 KB Output is correct
3 Correct 13 ms 22480 KB Output is correct
4 Correct 16 ms 27632 KB Output is correct
5 Correct 5 ms 14428 KB Output is correct
6 Correct 5 ms 14684 KB Output is correct
7 Correct 37 ms 42036 KB Output is correct
8 Correct 29 ms 38228 KB Output is correct
9 Correct 29 ms 42064 KB Output is correct
10 Correct 26 ms 36444 KB Output is correct
11 Correct 28 ms 38996 KB Output is correct
12 Correct 28 ms 40244 KB Output is correct
13 Correct 33 ms 51268 KB Output is correct
14 Correct 49 ms 58196 KB Output is correct
15 Correct 29 ms 37980 KB Output is correct
16 Correct 44 ms 58188 KB Output is correct
17 Correct 17 ms 28504 KB Output is correct
18 Correct 25 ms 35080 KB Output is correct
19 Correct 6 ms 15396 KB Output is correct
20 Correct 6 ms 15452 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22108 KB Output is correct
2 Correct 21 ms 31892 KB Output is correct
3 Correct 13 ms 22480 KB Output is correct
4 Correct 16 ms 27632 KB Output is correct
5 Correct 5 ms 14428 KB Output is correct
6 Correct 5 ms 14684 KB Output is correct
7 Correct 37 ms 42036 KB Output is correct
8 Correct 29 ms 38228 KB Output is correct
9 Correct 29 ms 42064 KB Output is correct
10 Correct 26 ms 36444 KB Output is correct
11 Correct 28 ms 38996 KB Output is correct
12 Correct 28 ms 40244 KB Output is correct
13 Correct 33 ms 51268 KB Output is correct
14 Correct 49 ms 58196 KB Output is correct
15 Correct 29 ms 37980 KB Output is correct
16 Correct 44 ms 58188 KB Output is correct
17 Correct 17 ms 28504 KB Output is correct
18 Correct 25 ms 35080 KB Output is correct
19 Correct 6 ms 15396 KB Output is correct
20 Correct 6 ms 15452 KB Output is correct
21 Correct 18 ms 30044 KB Output is correct
22 Correct 19 ms 31580 KB Output is correct
23 Correct 11 ms 21340 KB Output is correct
24 Correct 14 ms 24924 KB Output is correct
25 Correct 6 ms 14648 KB Output is correct
26 Correct 5 ms 14680 KB Output is correct
27 Correct 27 ms 36444 KB Output is correct
28 Correct 30 ms 41052 KB Output is correct
29 Correct 26 ms 36088 KB Output is correct
30 Correct 27 ms 35932 KB Output is correct
31 Correct 29 ms 42064 KB Output is correct
32 Correct 31 ms 42076 KB Output is correct
33 Correct 41 ms 50356 KB Output is correct
34 Correct 49 ms 58304 KB Output is correct
35 Correct 31 ms 46940 KB Output is correct
36 Correct 52 ms 58964 KB Output is correct
37 Correct 6 ms 14940 KB Output is correct
38 Correct 7 ms 15196 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 593 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 718 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 11 ms 22108 KB Output is correct
2 Correct 21 ms 31892 KB Output is correct
3 Correct 13 ms 22480 KB Output is correct
4 Correct 16 ms 27632 KB Output is correct
5 Correct 5 ms 14428 KB Output is correct
6 Correct 5 ms 14684 KB Output is correct
7 Correct 37 ms 42036 KB Output is correct
8 Correct 29 ms 38228 KB Output is correct
9 Correct 29 ms 42064 KB Output is correct
10 Correct 26 ms 36444 KB Output is correct
11 Correct 28 ms 38996 KB Output is correct
12 Correct 28 ms 40244 KB Output is correct
13 Correct 33 ms 51268 KB Output is correct
14 Correct 49 ms 58196 KB Output is correct
15 Correct 29 ms 37980 KB Output is correct
16 Correct 44 ms 58188 KB Output is correct
17 Correct 17 ms 28504 KB Output is correct
18 Correct 25 ms 35080 KB Output is correct
19 Correct 6 ms 15396 KB Output is correct
20 Correct 6 ms 15452 KB Output is correct
21 Runtime error 593 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 17336 KB Output is correct
2 Correct 38 ms 19400 KB Output is correct
3 Correct 43 ms 19536 KB Output is correct
4 Correct 35 ms 17868 KB Output is correct
5 Correct 32 ms 18796 KB Output is correct
6 Correct 38 ms 19540 KB Output is correct
7 Correct 24 ms 17808 KB Output is correct
8 Correct 23 ms 18432 KB Output is correct
9 Correct 32 ms 18756 KB Output is correct
10 Correct 27 ms 18180 KB Output is correct
11 Correct 34 ms 19292 KB Output is correct
12 Correct 34 ms 19280 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22108 KB Output is correct
2 Correct 21 ms 31892 KB Output is correct
3 Correct 13 ms 22480 KB Output is correct
4 Correct 16 ms 27632 KB Output is correct
5 Correct 5 ms 14428 KB Output is correct
6 Correct 5 ms 14684 KB Output is correct
7 Correct 37 ms 42036 KB Output is correct
8 Correct 29 ms 38228 KB Output is correct
9 Correct 29 ms 42064 KB Output is correct
10 Correct 26 ms 36444 KB Output is correct
11 Correct 28 ms 38996 KB Output is correct
12 Correct 28 ms 40244 KB Output is correct
13 Correct 33 ms 51268 KB Output is correct
14 Correct 49 ms 58196 KB Output is correct
15 Correct 29 ms 37980 KB Output is correct
16 Correct 44 ms 58188 KB Output is correct
17 Correct 17 ms 28504 KB Output is correct
18 Correct 25 ms 35080 KB Output is correct
19 Correct 6 ms 15396 KB Output is correct
20 Correct 6 ms 15452 KB Output is correct
21 Correct 18 ms 30044 KB Output is correct
22 Correct 19 ms 31580 KB Output is correct
23 Correct 11 ms 21340 KB Output is correct
24 Correct 14 ms 24924 KB Output is correct
25 Correct 6 ms 14648 KB Output is correct
26 Correct 5 ms 14680 KB Output is correct
27 Correct 27 ms 36444 KB Output is correct
28 Correct 30 ms 41052 KB Output is correct
29 Correct 26 ms 36088 KB Output is correct
30 Correct 27 ms 35932 KB Output is correct
31 Correct 29 ms 42064 KB Output is correct
32 Correct 31 ms 42076 KB Output is correct
33 Correct 41 ms 50356 KB Output is correct
34 Correct 49 ms 58304 KB Output is correct
35 Correct 31 ms 46940 KB Output is correct
36 Correct 52 ms 58964 KB Output is correct
37 Correct 6 ms 14940 KB Output is correct
38 Correct 7 ms 15196 KB Output is correct
39 Runtime error 593 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 11 ms 22108 KB Output is correct
2 Correct 21 ms 31892 KB Output is correct
3 Correct 13 ms 22480 KB Output is correct
4 Correct 16 ms 27632 KB Output is correct
5 Correct 5 ms 14428 KB Output is correct
6 Correct 5 ms 14684 KB Output is correct
7 Correct 37 ms 42036 KB Output is correct
8 Correct 29 ms 38228 KB Output is correct
9 Correct 29 ms 42064 KB Output is correct
10 Correct 26 ms 36444 KB Output is correct
11 Correct 28 ms 38996 KB Output is correct
12 Correct 28 ms 40244 KB Output is correct
13 Correct 33 ms 51268 KB Output is correct
14 Correct 49 ms 58196 KB Output is correct
15 Correct 29 ms 37980 KB Output is correct
16 Correct 44 ms 58188 KB Output is correct
17 Correct 17 ms 28504 KB Output is correct
18 Correct 25 ms 35080 KB Output is correct
19 Correct 6 ms 15396 KB Output is correct
20 Correct 6 ms 15452 KB Output is correct
21 Correct 18 ms 30044 KB Output is correct
22 Correct 19 ms 31580 KB Output is correct
23 Correct 11 ms 21340 KB Output is correct
24 Correct 14 ms 24924 KB Output is correct
25 Correct 6 ms 14648 KB Output is correct
26 Correct 5 ms 14680 KB Output is correct
27 Correct 27 ms 36444 KB Output is correct
28 Correct 30 ms 41052 KB Output is correct
29 Correct 26 ms 36088 KB Output is correct
30 Correct 27 ms 35932 KB Output is correct
31 Correct 29 ms 42064 KB Output is correct
32 Correct 31 ms 42076 KB Output is correct
33 Correct 41 ms 50356 KB Output is correct
34 Correct 49 ms 58304 KB Output is correct
35 Correct 31 ms 46940 KB Output is correct
36 Correct 52 ms 58964 KB Output is correct
37 Correct 6 ms 14940 KB Output is correct
38 Correct 7 ms 15196 KB Output is correct
39 Runtime error 593 ms 524288 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -