oj.uz

Submission #538488

# Submission time Handle Problem Language Result Execution time Memory
538488 2022-03-17T03:09:38 Z Wayne_Yan Food Court (JOI21_foodcourt) C++17
0 / 100
 1000 ms 64576 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 = 2010;
  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";
      }
    }
  }
}
namespace sub3{
  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) sub3::solve();
  
  return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 51760 KB Output is correct
2 Correct 48 ms 52208 KB Output is correct
3 Correct 52 ms 58916 KB Output is correct
4 Correct 59 ms 62376 KB Output is correct
5 Incorrect 32 ms 51316 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 51760 KB Output is correct
2 Correct 48 ms 52208 KB Output is correct
3 Correct 52 ms 58916 KB Output is correct
4 Correct 59 ms 62376 KB Output is correct
5 Incorrect 32 ms 51316 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 962 ms 55164 KB Output is correct
2 Correct 715 ms 55568 KB Output is correct
3 Correct 888 ms 55148 KB Output is correct
4 Correct 852 ms 55024 KB Output is correct
5 Correct 672 ms 55484 KB Output is correct
6 Correct 686 ms 55496 KB Output is correct
7 Correct 109 ms 54744 KB Output is correct
8 Correct 94 ms 54984 KB Output is correct
9 Execution timed out 1098 ms 55112 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 51760 KB Output is correct
2 Correct 48 ms 52208 KB Output is correct
3 Correct 52 ms 58916 KB Output is correct
4 Correct 59 ms 62376 KB Output is correct
5 Incorrect 32 ms 51316 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

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

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 51760 KB Output is correct
2 Correct 48 ms 52208 KB Output is correct
3 Correct 52 ms 58916 KB Output is correct
4 Correct 59 ms 62376 KB Output is correct
5 Incorrect 32 ms 51316 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 51760 KB Output is correct
2 Correct 48 ms 52208 KB Output is correct
3 Correct 52 ms 58916 KB Output is correct
4 Correct 59 ms 62376 KB Output is correct
5 Incorrect 32 ms 51316 KB Output isn't correct
6 Halted 0 ms 0 KB -