Submission #1206062

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

pokemonmaster

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 5e18
#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 = 1e5;
set<int> st[N];
vector<int> g[N], et;
indexed_set<pair<int,int>> seg[4*N];
int pr[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;

   pr[y] = x;
   g[x].push_back(y);
   up[y][0] = x;
}

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

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

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

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

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

int upd(int l, int r, int p, int q, int v){
   if(l == r){
      int x = seg[p].begin()->first;
      seg[p].clear();
      seg[p].insert({v, l});
      return x;
   }

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

   seg[p].erase({x, q});
   seg[p].insert({v, q});
   return x;
}

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

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, -1});

   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]];
   auto &u = st[x];
   u.erase(i);
   auto it = u.lower_bound(i);
   int z = *it;
   if(it != u.end()) seg_upd(*it, *prev(it));

   auto &w = st[v];
   it = w.lower_bound(i);
   if(it != w.end()) seg_upd(*it, i);
   w.insert(i);

   seg_upd(i, *----it);
}

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(pr, pr+N, 0);

   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=0; i <= N/2; i++) st[i].insert(-1);
   
   for(int i=0; i<2*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);
         upd(out[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: 0 / 24
• Subtask 5: 0 / 29