Submission #538494

#	Time	Username	Problem	Language	Result	Execution time	Memory
538494		Wayne_Yan	Food Court (JOI21_foodcourt)	C++17	0 / 100	1097 ms	104012 KiB

foodcourt

#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;
  deque<int> 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(curr[3]);
        }
      }
      if(curr[0] == 2){
        Fl(i, curr[1], curr[2]+1){
          int K = curr[3];
          if(shop[i].size() <= K) shop[i].clear();
          else{
            F(K) shop[i].pop_front();
          }
        }
      }
      if(curr[0] == 3){
        if( shop[curr[1]].size() >= curr[2]){
          cout << shop[curr[1]][curr[2]-1];
        }else{
          cout << 0;
        }
        cout << "\n";
      }
    }
  }
}

namespace sub2{
  const int maxN = 2e3+10;
  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 || qs[i][4] != 1)){
      __sub3 = false; 
    }
  }

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

Compilation message (stderr)

foodcourt.cpp: In function 'void sub3::solve()':
foodcourt.cpp:51:29: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   51 |           if(shop[i].size() <= K) shop[i].clear();
      |              ~~~~~~~~~~~~~~~^~~~
foodcourt.cpp:58:34: warning: comparison of integer expressions of different signedness: 'std::deque<long long int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} [-Wsign-compare]
   58 |         if( shop[curr[1]].size() >= curr[2]){

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11