oj.uz

Submission #538487

# Submission time Handle Problem Language Result Execution time Memory
538487 2022-03-17T03:07:59 Z Wayne_Yan Food Court (JOI21_foodcourt) C++17
0 / 100
 1000 ms 63028 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 sub2{
  const int maxN = 65010;
  deque<pii> shop[maxN];
  
  void solve(){
    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();
  bool __sub3 = true;
  F(Q){
    if(qs[i][0] == 1 && qs[i][2] - qs[i][1] > 10){
      __sub3 = false; 
    }
  }

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

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 50420 KB Output is correct
2 Correct 44 ms 50848 KB Output is correct
3 Correct 48 ms 57372 KB Output is correct
4 Correct 54 ms 60952 KB Output is correct
5 Incorrect 32 ms 50004 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 50420 KB Output is correct
2 Correct 44 ms 50848 KB Output is correct
3 Correct 48 ms 57372 KB Output is correct
4 Correct 54 ms 60952 KB Output is correct
5 Incorrect 32 ms 50004 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 53928 KB Output is correct
2 Correct 703 ms 55376 KB Output is correct
3 Correct 776 ms 54876 KB Output is correct
4 Correct 784 ms 54964 KB Output is correct
5 Correct 599 ms 55372 KB Output is correct
6 Correct 588 ms 55264 KB Output is correct
7 Correct 87 ms 54224 KB Output is correct
8 Correct 91 ms 54392 KB Output is correct
9 Execution timed out 1083 ms 55096 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 313 ms 63028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 50420 KB Output is correct
2 Correct 44 ms 50848 KB Output is correct
3 Correct 48 ms 57372 KB Output is correct
4 Correct 54 ms 60952 KB Output is correct
5 Incorrect 32 ms 50004 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 53560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 50420 KB Output is correct
2 Correct 44 ms 50848 KB Output is correct
3 Correct 48 ms 57372 KB Output is correct
4 Correct 54 ms 60952 KB Output is correct
5 Incorrect 32 ms 50004 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 50420 KB Output is correct
2 Correct 44 ms 50848 KB Output is correct
3 Correct 48 ms 57372 KB Output is correct
4 Correct 54 ms 60952 KB Output is correct
5 Incorrect 32 ms 50004 KB Output isn't correct
6 Halted 0 ms 0 KB -