Submission #1206183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206183		loom	I want to be the very best too! (NOI17_pokemonmaster)	C++20	100 / 100	2786 ms	76060 KiB

pokemonmaster

#pragma GCC optimize("Ofast", "unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'

using namespace __gnu_pbds;
template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 5e4+1;
set<int> st[N];
vector<int> g[N], et;
indexed_set<int> seg[4*N];
int mx[N], pr[N], sz[N], pt[N], lt[N], in[N], out[N], lst[N], up[N][16];

int find(int x){
   return x == pr[x] ? x : (pr[x] = find(pr[x]));
}

void unite(int x, int y){
   x = find(x);
   y = find(y);
   if(x == y) return;
   
   g[mx[x]].push_back(mx[y]);

   if(sz[x] < sz[y]) swap(x, y);
   mx[x] = max(mx[x], mx[y]);
   pr[y] = x;
   sz[x] += sz[y];
}

void dfs(int v){
   in[v] = et.size();
   et.push_back(v);

   for(int ch : g[v]){
      up[ch][0] = v;
      dfs(ch);
   }

   out[v] = et.size()-1;
}

void build(int l, int r, int p){
   if(l == r){
      seg[p].insert(lst[l]);
      return;
   }

   int m = (l+r)/2;
   build(l, m, p*2);
   build(m+1, r, p*2+1);
   
   for(int x : seg[p*2]) seg[p].insert(x);
   for(int x : seg[p*2+1]) seg[p].insert(x);
}

int upd(int l, int r, int p, int q, int v, int ix){
   if(l == r){
      int x = *seg[p].begin();
      seg[p].erase(x);
      seg[p].insert(v);
      return x;
   }

   int m = (l+r)/2, x;
   if(q <= m) x = upd(l, m, p*2, q, v, ix);
   else x = upd(m+1, r, p*2+1, q, v, ix);

   if(r < ix or ix < l) seg[p].erase(x);
   seg[p].insert(v);
   return x;
}

void seg_upd(int q, int v, int ix){
   upd(0, N-1, 1, q, v, ix);
}

int qry(int l, int r, int p, int ql, int qr){
   if(r < ql or qr < l) return 0;
   if(ql <= l and r <= qr) return seg[p].order_of_key(ql);

   int m = (l+r)/2;
   return qry(l, m, p*2, ql, qr) + qry(m+1, r, p*2+1, ql, qr);
}

int qry(int ql, int qr){
   return qry(0, N-1, 1, ql, qr);
}

void upd(int i, int v){
   int x = pt[et[i]], tf = 0;

   auto &u = st[x];
   u.erase(i);
   auto it = u.lower_bound(i);
   if(it != u.end()) seg_upd(*it, *prev(it), -1), tf = 1;
   int pos = *it;

   auto &w = st[v];
   w.insert(i);
   it = w.find(i);
   if(next(it) != w.end()) seg_upd(*next(it), i, -1);
   
   seg_upd(i, *prev(it), (tf ? pos : -1));
}

inline void solve(){
   int n, m, q;
   cin>>n>>m>>q;
   int tot = n*m;

   int l[n+1][m+1];
   vector<tuple<int,int,int>> v;

   for(int i=1; i<=n; i++){
      for(int j=1; j<=m; j++){
         cin>>l[i][j];
         v.push_back({l[i][j], i, j});
      }
   }
   sort(v.begin(), v.end());

   int p[n+1][m+1];
   for(int i=1; i<=n; i++){
      for(int j=1; j<=m; j++){
         cin>>p[i][j];
      }
   }

   iota(mx, mx+N, 0);
   iota(pr, pr+N, 0);
   fill(sz, sz+N, 1);

   int ix[n+1][m+1];
   for(int i=0; i<tot; i++){
      auto [x, a, b] = v[i];
      ix[a][b] = i;
      pt[i] = p[a][b];
      lt[i] = l[a][b];

      if(a+1 <= n and l[a+1][b] < x) unite(i, ix[a+1][b]);
      if(a-1 > 0 and l[a-1][b] < x) unite(i, ix[a-1][b]);
      if(b+1 <= m and l[a][b+1] < x) unite(i, ix[a][b+1]);
      if(b-1 > 0 and l[a][b-1] < x) unite(i, ix[a][b-1]);
   }
   dfs(tot-1);

   up[tot-1][0] = tot-1;
   for(int j=1; j<16; j++){
      for(int i=0; i<tot; i++){
         up[i][j] = up[up[i][j-1]][j-1];
      }
   }

   for(int i=1; i<N; i++) st[i].insert(-i);
   
   for(int i=0; i<tot; i++){
      int x = pt[et[i]];
      lst[i] = *st[x].rbegin();
      st[x].insert(i);
   }
   build(0, N-1, 1);

   while(q--){
      int w, x, y, v;
      cin>>w>>x>>y>>v;
      swap(x, y);
      int pos = ix[x][y];

      if(w == 1){
         upd(in[pos], v);
         pt[pos] = v;
         continue;
      }

      if(lt[pos] > v){
         cout<<0<<nl;
         continue;
      }
      
      for(int i=15; i>=0; i--){
         if(lt[up[pos][i]] <= v) pos = up[pos][i];
      }

      cout<<qry(in[pos], out[pos])<<nl;
   }
}

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

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 29 / 29