oj.uz

Submission #538517

# Submission time Handle Problem Language Result Execution time Memory
538517 2022-03-17T03:44:05 Z Wayne_Yan Food Court (JOI21_foodcourt) C++17
7 / 100
 1000 ms 62588 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];
          if((int)shop[i].size() <= K) shop[i].clear();
          else{
            Fi(j, K) shop[i].pop_front();
          }
        }
      }
      if(curr[0] == 3){
        deque<int> now = shop[curr[1]];
        if( (int)now.size() >= curr[2]){
          cout << now[curr[2]-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 >> 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 47 ms 50388 KB Output is correct
2 Correct 52 ms 50832 KB Output is correct
3 Correct 50 ms 57432 KB Output is correct
4 Correct 55 ms 61004 KB Output is correct
5 Correct 43 ms 50000 KB Output is correct
6 Correct 33 ms 50004 KB Output is correct
7 Correct 52 ms 62588 KB Output is correct
8 Correct 57 ms 58188 KB Output is correct
9 Correct 46 ms 50764 KB Output is correct
10 Correct 64 ms 57560 KB Output is correct
11 Correct 49 ms 54788 KB Output is correct
12 Correct 45 ms 50960 KB Output is correct
13 Correct 45 ms 50900 KB Output is correct
14 Correct 50 ms 52108 KB Output is correct
15 Correct 54 ms 52940 KB Output is correct
16 Correct 51 ms 52076 KB Output is correct
17 Correct 39 ms 50388 KB Output is correct
18 Correct 44 ms 50508 KB Output is correct
19 Correct 41 ms 50000 KB Output is correct
20 Correct 41 ms 50064 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 50388 KB Output is correct
2 Correct 52 ms 50832 KB Output is correct
3 Correct 50 ms 57432 KB Output is correct
4 Correct 55 ms 61004 KB Output is correct
5 Correct 43 ms 50000 KB Output is correct
6 Correct 33 ms 50004 KB Output is correct
7 Correct 52 ms 62588 KB Output is correct
8 Correct 57 ms 58188 KB Output is correct
9 Correct 46 ms 50764 KB Output is correct
10 Correct 64 ms 57560 KB Output is correct
11 Correct 49 ms 54788 KB Output is correct
12 Correct 45 ms 50960 KB Output is correct
13 Correct 45 ms 50900 KB Output is correct
14 Correct 50 ms 52108 KB Output is correct
15 Correct 54 ms 52940 KB Output is correct
16 Correct 51 ms 52076 KB Output is correct
17 Correct 39 ms 50388 KB Output is correct
18 Correct 44 ms 50508 KB Output is correct
19 Correct 41 ms 50000 KB Output is correct
20 Correct 41 ms 50064 KB Output is correct
21 Correct 43 ms 50724 KB Output is correct
22 Correct 48 ms 50900 KB Output is correct
23 Correct 49 ms 57396 KB Output is correct
24 Correct 56 ms 61056 KB Output is correct
25 Correct 34 ms 50012 KB Output is correct
26 Correct 32 ms 50044 KB Output is correct
27 Correct 61 ms 61956 KB Output is correct
28 Correct 60 ms 58828 KB Output is correct
29 Correct 56 ms 52564 KB Output is correct
30 Correct 55 ms 57172 KB Output is correct
31 Correct 54 ms 54624 KB Output is correct
32 Correct 48 ms 50692 KB Output is correct
33 Correct 52 ms 50876 KB Output is correct
34 Correct 60 ms 53048 KB Output is correct
35 Correct 51 ms 51596 KB Output is correct
36 Correct 55 ms 51952 KB Output is correct
37 Correct 34 ms 50004 KB Output is correct
38 Correct 37 ms 50056 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 886 ms 53660 KB Output is correct
2 Correct 656 ms 54616 KB Output is correct
3 Correct 893 ms 54260 KB Output is correct
4 Correct 898 ms 54276 KB Output is correct
5 Correct 677 ms 54596 KB Output is correct
6 Correct 684 ms 54564 KB Output is correct
7 Correct 87 ms 54052 KB Output is correct
8 Correct 95 ms 54196 KB Output is correct
9 Execution timed out 1085 ms 54504 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 301 ms 38956 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 47 ms 50388 KB Output is correct
2 Correct 52 ms 50832 KB Output is correct
3 Correct 50 ms 57432 KB Output is correct
4 Correct 55 ms 61004 KB Output is correct
5 Correct 43 ms 50000 KB Output is correct
6 Correct 33 ms 50004 KB Output is correct
7 Correct 52 ms 62588 KB Output is correct
8 Correct 57 ms 58188 KB Output is correct
9 Correct 46 ms 50764 KB Output is correct
10 Correct 64 ms 57560 KB Output is correct
11 Correct 49 ms 54788 KB Output is correct
12 Correct 45 ms 50960 KB Output is correct
13 Correct 45 ms 50900 KB Output is correct
14 Correct 50 ms 52108 KB Output is correct
15 Correct 54 ms 52940 KB Output is correct
16 Correct 51 ms 52076 KB Output is correct
17 Correct 39 ms 50388 KB Output is correct
18 Correct 44 ms 50508 KB Output is correct
19 Correct 41 ms 50000 KB Output is correct
20 Correct 41 ms 50064 KB Output is correct
21 Correct 886 ms 53660 KB Output is correct
22 Correct 656 ms 54616 KB Output is correct
23 Correct 893 ms 54260 KB Output is correct
24 Correct 898 ms 54276 KB Output is correct
25 Correct 677 ms 54596 KB Output is correct
26 Correct 684 ms 54564 KB Output is correct
27 Correct 87 ms 54052 KB Output is correct
28 Correct 95 ms 54196 KB Output is correct
29 Execution timed out 1085 ms 54504 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 95 ms 19572 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 47 ms 50388 KB Output is correct
2 Correct 52 ms 50832 KB Output is correct
3 Correct 50 ms 57432 KB Output is correct
4 Correct 55 ms 61004 KB Output is correct
5 Correct 43 ms 50000 KB Output is correct
6 Correct 33 ms 50004 KB Output is correct
7 Correct 52 ms 62588 KB Output is correct
8 Correct 57 ms 58188 KB Output is correct
9 Correct 46 ms 50764 KB Output is correct
10 Correct 64 ms 57560 KB Output is correct
11 Correct 49 ms 54788 KB Output is correct
12 Correct 45 ms 50960 KB Output is correct
13 Correct 45 ms 50900 KB Output is correct
14 Correct 50 ms 52108 KB Output is correct
15 Correct 54 ms 52940 KB Output is correct
16 Correct 51 ms 52076 KB Output is correct
17 Correct 39 ms 50388 KB Output is correct
18 Correct 44 ms 50508 KB Output is correct
19 Correct 41 ms 50000 KB Output is correct
20 Correct 41 ms 50064 KB Output is correct
21 Correct 43 ms 50724 KB Output is correct
22 Correct 48 ms 50900 KB Output is correct
23 Correct 49 ms 57396 KB Output is correct
24 Correct 56 ms 61056 KB Output is correct
25 Correct 34 ms 50012 KB Output is correct
26 Correct 32 ms 50044 KB Output is correct
27 Correct 61 ms 61956 KB Output is correct
28 Correct 60 ms 58828 KB Output is correct
29 Correct 56 ms 52564 KB Output is correct
30 Correct 55 ms 57172 KB Output is correct
31 Correct 54 ms 54624 KB Output is correct
32 Correct 48 ms 50692 KB Output is correct
33 Correct 52 ms 50876 KB Output is correct
34 Correct 60 ms 53048 KB Output is correct
35 Correct 51 ms 51596 KB Output is correct
36 Correct 55 ms 51952 KB Output is correct
37 Correct 34 ms 50004 KB Output is correct
38 Correct 37 ms 50056 KB Output is correct
39 Correct 886 ms 53660 KB Output is correct
40 Correct 656 ms 54616 KB Output is correct
41 Correct 893 ms 54260 KB Output is correct
42 Correct 898 ms 54276 KB Output is correct
43 Correct 677 ms 54596 KB Output is correct
44 Correct 684 ms 54564 KB Output is correct
45 Correct 87 ms 54052 KB Output is correct
46 Correct 95 ms 54196 KB Output is correct
47 Execution timed out 1085 ms 54504 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 50388 KB Output is correct
2 Correct 52 ms 50832 KB Output is correct
3 Correct 50 ms 57432 KB Output is correct
4 Correct 55 ms 61004 KB Output is correct
5 Correct 43 ms 50000 KB Output is correct
6 Correct 33 ms 50004 KB Output is correct
7 Correct 52 ms 62588 KB Output is correct
8 Correct 57 ms 58188 KB Output is correct
9 Correct 46 ms 50764 KB Output is correct
10 Correct 64 ms 57560 KB Output is correct
11 Correct 49 ms 54788 KB Output is correct
12 Correct 45 ms 50960 KB Output is correct
13 Correct 45 ms 50900 KB Output is correct
14 Correct 50 ms 52108 KB Output is correct
15 Correct 54 ms 52940 KB Output is correct
16 Correct 51 ms 52076 KB Output is correct
17 Correct 39 ms 50388 KB Output is correct
18 Correct 44 ms 50508 KB Output is correct
19 Correct 41 ms 50000 KB Output is correct
20 Correct 41 ms 50064 KB Output is correct
21 Correct 43 ms 50724 KB Output is correct
22 Correct 48 ms 50900 KB Output is correct
23 Correct 49 ms 57396 KB Output is correct
24 Correct 56 ms 61056 KB Output is correct
25 Correct 34 ms 50012 KB Output is correct
26 Correct 32 ms 50044 KB Output is correct
27 Correct 61 ms 61956 KB Output is correct
28 Correct 60 ms 58828 KB Output is correct
29 Correct 56 ms 52564 KB Output is correct
30 Correct 55 ms 57172 KB Output is correct
31 Correct 54 ms 54624 KB Output is correct
32 Correct 48 ms 50692 KB Output is correct
33 Correct 52 ms 50876 KB Output is correct
34 Correct 60 ms 53048 KB Output is correct
35 Correct 51 ms 51596 KB Output is correct
36 Correct 55 ms 51952 KB Output is correct
37 Correct 34 ms 50004 KB Output is correct
38 Correct 37 ms 50056 KB Output is correct
39 Correct 886 ms 53660 KB Output is correct
40 Correct 656 ms 54616 KB Output is correct
41 Correct 893 ms 54260 KB Output is correct
42 Correct 898 ms 54276 KB Output is correct
43 Correct 677 ms 54596 KB Output is correct
44 Correct 684 ms 54564 KB Output is correct
45 Correct 87 ms 54052 KB Output is correct
46 Correct 95 ms 54196 KB Output is correct
47 Execution timed out 1085 ms 54504 KB Time limit exceeded
48 Halted 0 ms 0 KB -