oj.uz

Submission #538521

# Submission time Handle Problem Language Result Execution time Memory
538521 2022-03-17T03:48:52 Z Wayne_Yan Food Court (JOI21_foodcourt) C++17
7 / 100
 1000 ms 62544 KB 
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int maxN = 250010;
vector<int> qs[maxN];
int N,M,Q;

namespace sub3{
  const int maxN = 65010;

  void solve(){
    deque<int> shop[maxN];
    Fi(j, Q){
      vector<int> curr = qs[j];
      if(curr[0] == 1){
        Fl(i, curr[1], curr[2]+1){
          shop[i].push_back(curr[3]);
        }
      }
      if(curr[0] == 2){
        Fl(i, curr[1], curr[2]+1){
          int K = curr[3];
          while(!shop[i].empty() && K){
            shop[i].pop_front();
            K--;
          }
        }
      }
      if(curr[0] == 3){
        int b = curr[2];
        deque<int> now = shop[curr[1]];
        if( (int)now.size() >= b){
          cout << now[b-1];
        }else{
          cout << 0;
        }
        cout << "\n";
      }
    }
  }
}

namespace sub2{
  const int maxN = 65010;
  
  void solve(){
    deque<pii> shop[maxN];
    Fi(j, Q){
      vector<int> curr = qs[j];
      if(curr[0] == 1){
        Fl(i, curr[1], curr[2]+1){
          shop[i].push_back(mp(curr[3], curr[4]));
        }
      }
      if(curr[0] == 2){
        Fl(i, curr[1], curr[2]+1){
          int K = curr[3];
          while(!shop[i].empty() && K){
            if(shop[i][0].ss > K){
              shop[i][0].ss -= K;
              K = 0; 
            }else{
              K -= shop[i][0].ss;
              shop[i].pop_front();
            }
          }
        }
      }
      if(curr[0] == 3){
        int b = curr[2];
        deque<pii> now = shop[curr[1]];
        for(pii p : now){
          if(b <= p.ss){
            cout << p.ff << "\n";
            b = 0;
            break;
          }else{
            b -= p.ss;
          }
        }
        if(b) cout << "0\n";
      }
    }
  }
}

signed main(){
  
  cin.tie(0);
  ios_base::sync_with_stdio(false);


  cin >> N >> M >> Q;
  int x;
  F(Q){
    int t;
    cin >> t;
    qs[i].pb(t);
    Fi(j, 5-t){
      cin >> x;
      qs[i].pb(x);
    }
  }
  
  if(N <= 2000 && Q <= 2000){
    sub2::solve(); 
    return 0;
  }

  bool __sub3 = true;
  F(Q){
    if(qs[i][0] == 1 && (qs[i][2] - qs[i][1] > 10 || qs[i][4] != 1)){
      __sub3 = false; 
    }
  }

  if( N <= 65000 && Q <= 65000 && __sub3){
    sub2::solve();
    return 0;
  }

  assert(0);

  return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 50412 KB Output is correct
2 Correct 42 ms 50872 KB Output is correct
3 Correct 49 ms 57348 KB Output is correct
4 Correct 57 ms 61040 KB Output is correct
5 Correct 31 ms 49996 KB Output is correct
6 Correct 31 ms 49992 KB Output is correct
7 Correct 51 ms 62544 KB Output is correct
8 Correct 51 ms 58212 KB Output is correct
9 Correct 44 ms 50848 KB Output is correct
10 Correct 52 ms 57780 KB Output is correct
11 Correct 50 ms 54732 KB Output is correct
12 Correct 44 ms 50988 KB Output is correct
13 Correct 42 ms 50900 KB Output is correct
14 Correct 48 ms 52244 KB Output is correct
15 Correct 46 ms 52940 KB Output is correct
16 Correct 60 ms 52116 KB Output is correct
17 Correct 39 ms 50392 KB Output is correct
18 Correct 40 ms 50572 KB Output is correct
19 Correct 33 ms 49996 KB Output is correct
20 Correct 34 ms 50064 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 50412 KB Output is correct
2 Correct 42 ms 50872 KB Output is correct
3 Correct 49 ms 57348 KB Output is correct
4 Correct 57 ms 61040 KB Output is correct
5 Correct 31 ms 49996 KB Output is correct
6 Correct 31 ms 49992 KB Output is correct
7 Correct 51 ms 62544 KB Output is correct
8 Correct 51 ms 58212 KB Output is correct
9 Correct 44 ms 50848 KB Output is correct
10 Correct 52 ms 57780 KB Output is correct
11 Correct 50 ms 54732 KB Output is correct
12 Correct 44 ms 50988 KB Output is correct
13 Correct 42 ms 50900 KB Output is correct
14 Correct 48 ms 52244 KB Output is correct
15 Correct 46 ms 52940 KB Output is correct
16 Correct 60 ms 52116 KB Output is correct
17 Correct 39 ms 50392 KB Output is correct
18 Correct 40 ms 50572 KB Output is correct
19 Correct 33 ms 49996 KB Output is correct
20 Correct 34 ms 50064 KB Output is correct
21 Correct 41 ms 50676 KB Output is correct
22 Correct 41 ms 50948 KB Output is correct
23 Correct 50 ms 57316 KB Output is correct
24 Correct 63 ms 61116 KB Output is correct
25 Correct 36 ms 50064 KB Output is correct
26 Correct 34 ms 49964 KB Output is correct
27 Correct 53 ms 62004 KB Output is correct
28 Correct 55 ms 58956 KB Output is correct
29 Correct 52 ms 52552 KB Output is correct
30 Correct 58 ms 57160 KB Output is correct
31 Correct 52 ms 54604 KB Output is correct
32 Correct 45 ms 50772 KB Output is correct
33 Correct 49 ms 50872 KB Output is correct
34 Correct 59 ms 53120 KB Output is correct
35 Correct 48 ms 51612 KB Output is correct
36 Correct 52 ms 52112 KB Output is correct
37 Correct 44 ms 49968 KB Output is correct
38 Correct 44 ms 50016 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 53800 KB Output is correct
2 Correct 615 ms 53940 KB Output is correct
3 Correct 847 ms 53684 KB Output is correct
4 Correct 844 ms 53700 KB Output is correct
5 Correct 682 ms 54032 KB Output is correct
6 Correct 652 ms 54020 KB Output is correct
7 Correct 61 ms 53440 KB Output is correct
8 Correct 78 ms 53540 KB Output is correct
9 Execution timed out 1093 ms 53852 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 127 ms 38984 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 50412 KB Output is correct
2 Correct 42 ms 50872 KB Output is correct
3 Correct 49 ms 57348 KB Output is correct
4 Correct 57 ms 61040 KB Output is correct
5 Correct 31 ms 49996 KB Output is correct
6 Correct 31 ms 49992 KB Output is correct
7 Correct 51 ms 62544 KB Output is correct
8 Correct 51 ms 58212 KB Output is correct
9 Correct 44 ms 50848 KB Output is correct
10 Correct 52 ms 57780 KB Output is correct
11 Correct 50 ms 54732 KB Output is correct
12 Correct 44 ms 50988 KB Output is correct
13 Correct 42 ms 50900 KB Output is correct
14 Correct 48 ms 52244 KB Output is correct
15 Correct 46 ms 52940 KB Output is correct
16 Correct 60 ms 52116 KB Output is correct
17 Correct 39 ms 50392 KB Output is correct
18 Correct 40 ms 50572 KB Output is correct
19 Correct 33 ms 49996 KB Output is correct
20 Correct 34 ms 50064 KB Output is correct
21 Correct 830 ms 53800 KB Output is correct
22 Correct 615 ms 53940 KB Output is correct
23 Correct 847 ms 53684 KB Output is correct
24 Correct 844 ms 53700 KB Output is correct
25 Correct 682 ms 54032 KB Output is correct
26 Correct 652 ms 54020 KB Output is correct
27 Correct 61 ms 53440 KB Output is correct
28 Correct 78 ms 53540 KB Output is correct
29 Execution timed out 1093 ms 53852 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 19744 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 50412 KB Output is correct
2 Correct 42 ms 50872 KB Output is correct
3 Correct 49 ms 57348 KB Output is correct
4 Correct 57 ms 61040 KB Output is correct
5 Correct 31 ms 49996 KB Output is correct
6 Correct 31 ms 49992 KB Output is correct
7 Correct 51 ms 62544 KB Output is correct
8 Correct 51 ms 58212 KB Output is correct
9 Correct 44 ms 50848 KB Output is correct
10 Correct 52 ms 57780 KB Output is correct
11 Correct 50 ms 54732 KB Output is correct
12 Correct 44 ms 50988 KB Output is correct
13 Correct 42 ms 50900 KB Output is correct
14 Correct 48 ms 52244 KB Output is correct
15 Correct 46 ms 52940 KB Output is correct
16 Correct 60 ms 52116 KB Output is correct
17 Correct 39 ms 50392 KB Output is correct
18 Correct 40 ms 50572 KB Output is correct
19 Correct 33 ms 49996 KB Output is correct
20 Correct 34 ms 50064 KB Output is correct
21 Correct 41 ms 50676 KB Output is correct
22 Correct 41 ms 50948 KB Output is correct
23 Correct 50 ms 57316 KB Output is correct
24 Correct 63 ms 61116 KB Output is correct
25 Correct 36 ms 50064 KB Output is correct
26 Correct 34 ms 49964 KB Output is correct
27 Correct 53 ms 62004 KB Output is correct
28 Correct 55 ms 58956 KB Output is correct
29 Correct 52 ms 52552 KB Output is correct
30 Correct 58 ms 57160 KB Output is correct
31 Correct 52 ms 54604 KB Output is correct
32 Correct 45 ms 50772 KB Output is correct
33 Correct 49 ms 50872 KB Output is correct
34 Correct 59 ms 53120 KB Output is correct
35 Correct 48 ms 51612 KB Output is correct
36 Correct 52 ms 52112 KB Output is correct
37 Correct 44 ms 49968 KB Output is correct
38 Correct 44 ms 50016 KB Output is correct
39 Correct 830 ms 53800 KB Output is correct
40 Correct 615 ms 53940 KB Output is correct
41 Correct 847 ms 53684 KB Output is correct
42 Correct 844 ms 53700 KB Output is correct
43 Correct 682 ms 54032 KB Output is correct
44 Correct 652 ms 54020 KB Output is correct
45 Correct 61 ms 53440 KB Output is correct
46 Correct 78 ms 53540 KB Output is correct
47 Execution timed out 1093 ms 53852 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 50412 KB Output is correct
2 Correct 42 ms 50872 KB Output is correct
3 Correct 49 ms 57348 KB Output is correct
4 Correct 57 ms 61040 KB Output is correct
5 Correct 31 ms 49996 KB Output is correct
6 Correct 31 ms 49992 KB Output is correct
7 Correct 51 ms 62544 KB Output is correct
8 Correct 51 ms 58212 KB Output is correct
9 Correct 44 ms 50848 KB Output is correct
10 Correct 52 ms 57780 KB Output is correct
11 Correct 50 ms 54732 KB Output is correct
12 Correct 44 ms 50988 KB Output is correct
13 Correct 42 ms 50900 KB Output is correct
14 Correct 48 ms 52244 KB Output is correct
15 Correct 46 ms 52940 KB Output is correct
16 Correct 60 ms 52116 KB Output is correct
17 Correct 39 ms 50392 KB Output is correct
18 Correct 40 ms 50572 KB Output is correct
19 Correct 33 ms 49996 KB Output is correct
20 Correct 34 ms 50064 KB Output is correct
21 Correct 41 ms 50676 KB Output is correct
22 Correct 41 ms 50948 KB Output is correct
23 Correct 50 ms 57316 KB Output is correct
24 Correct 63 ms 61116 KB Output is correct
25 Correct 36 ms 50064 KB Output is correct
26 Correct 34 ms 49964 KB Output is correct
27 Correct 53 ms 62004 KB Output is correct
28 Correct 55 ms 58956 KB Output is correct
29 Correct 52 ms 52552 KB Output is correct
30 Correct 58 ms 57160 KB Output is correct
31 Correct 52 ms 54604 KB Output is correct
32 Correct 45 ms 50772 KB Output is correct
33 Correct 49 ms 50872 KB Output is correct
34 Correct 59 ms 53120 KB Output is correct
35 Correct 48 ms 51612 KB Output is correct
36 Correct 52 ms 52112 KB Output is correct
37 Correct 44 ms 49968 KB Output is correct
38 Correct 44 ms 50016 KB Output is correct
39 Correct 830 ms 53800 KB Output is correct
40 Correct 615 ms 53940 KB Output is correct
41 Correct 847 ms 53684 KB Output is correct
42 Correct 844 ms 53700 KB Output is correct
43 Correct 682 ms 54032 KB Output is correct
44 Correct 652 ms 54020 KB Output is correct
45 Correct 61 ms 53440 KB Output is correct
46 Correct 78 ms 53540 KB Output is correct
47 Execution timed out 1093 ms 53852 KB Time limit exceeded
48 Halted 0 ms 0 KB -