Submission #999530

#	Time	Username	Problem	Language	Result	Execution time	Memory
999530		cadmiumsky	Seats (IOI18_seats)	C++17	11 / 100	4069 ms	189700 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#define all(x) (x).begin(),(x).end()
using namespace std;
using pii = pair<int,int>;

#define sz(x) ((int)(x).size())

template<typename Node> 
struct AINT {
   vector<Node> aint;
   int n;
   void init(int n_) {
      n = n_;
      aint.assign(2 * n + 5, Node());
   }
   
   template<class CB> void walk(CB&& cb) { walk(cb, 0, n); }
   template<class CB> void walk(CB&& cb, int l, int r) { walk(cb, l, r, 1, 0, n); }
   template<class CB> void walk(CB&& cb, int l, int r, int node, int cl, int cr) {
      if(cr < l || r < cl) return;
      if(l <= cl && cr <= r && !cb(aint[node], cl, cr)) return;
      int mid = (cl + cr) >> 1, L = node + 1, R = node + (mid - cl + 1) * 2;
      aint[node].push(aint[L], aint[R]);
      walk(cb, l, r, L, cl, mid);
      walk(cb, l, r, R, mid + 1, cr);
      aint[node].pull(aint[L], aint[R]);
   }
};

const int necesar = 1;


struct nmns : vector<pii> {
   void pull(const nmns& L, const nmns& R) {
      map<int, int> f;
      for(auto [a, b] : L) f[a] += b;
      for(auto [a, b] : R) f[a] += b;
      auto it = f.begin();
      clear();
      for(int i = 0; i < min(sz(f), necesar); i++) emplace_back(it -> first, it -> second), it = next(it);
   }
   void apply(int x) { for(auto &[a, b] : *this) a += x; }
};

struct Node {
   nmns val;
   int lazy;
   void push(Node& L, Node& R) {
      if(lazy == 0) return;
      L.val.apply(lazy);
      R.val.apply(lazy);
      L.lazy += lazy;
      R.lazy += lazy;
      lazy = 0;
   }
   
   void pull(const Node& L, const Node& R) {
      val.pull(L.val, R.val);
   }
};

AINT<Node> aint;

void add(int l, int r, int val) { 
   aint.walk([&](Node& node, int cl, int cr) { node.val.apply(val); node.lazy += val; return 0;}, l, r); 
}
int query() { 
   //aint.walk([&](Node& node, int cl, int cr) {  cerr << "--\n";  for(auto [a, b] : node.val) cerr << '\t' << a << ": " << b << '\n'; cerr << "--\n"; return 0;}, 2, 2);
   auto v = aint.aint[1].val;
   //aint.walk([&](Node& val, int cl, int cr) {
      //if(cl != cr) return 1;
      //cerr << val.val[0].first << ": " << val.val[0].second << ",\t";
      //return 0; 
   //});
   //cerr << '\n';
   
   for(auto [a, b] : v) {
      if(a == 4) return b;
   }
   assert(false);
   return -1;
}

vector<vector<int>> mat;
vector<int> R, C;
int H, W;

vector<vector<int>> added;

void modcorner(int i, int j, int aggr) {
   if(added[i][j] == aggr) return;
   added[i][j] = aggr;
   vector<int> val;
   val.emplace_back(mat[i][j]);
   val.emplace_back(mat[i + 1][j]);
   val.emplace_back(mat[i + 1][j + 1]);
   val.emplace_back(mat[i][j + 1]);
   sort(all(val));
   add(val[0], val[1] - 1, aggr);
   add(val[2], val[3] - 1, aggr);
   return;
}


void modcell(int i, int j, int aggr) {
   for(int a = -1; a <= 1; a++)
      for(int b = -1; b <= 1; b++)
         if(i + a >= 0 && i + a <= H && j + b >= 0 && j + b <= W)
            modcorner(i + a, j + b, aggr);
}

void give_initial_chart(int H_, int W_, std::vector<int> R_, std::vector<int> C_) {
   H = H_; W = W_; R = R_; C = C_;
   mat.assign(H + 2, vector<int>(W + 2, H * W + 1));
   added.assign(H + 2, vector<int>(W + 2, 0));
   for(auto &x : R) x++;
   for(auto &x : C) x++;
   for(int i = 0; i < H * W; i++) mat[R[i]][C[i]] = i;
   aint.init(H * W - 1);
   aint.walk([&](Node& val, int cl, int cr) {
      if(cl != cr) return 1;
      val.val.emplace_back(0, 1);
      return 0;
   });
   
   for(int i = 0; i <= H; i++)
      for(int j = 0; j <= W; j++)
         modcorner(i, j, 1);
}

int swap_seats(int a, int b) {
   auto [x, y] = make_pair(R[a], C[a]);
   auto [u, v] = make_pair(R[b], C[b]);
   swap(R[a], R[b]);
   swap(C[a], C[b]);
   modcell(x, y, -1);
   modcell(u, v, -1);
   swap(mat[x][y], mat[u][v]);
   modcell(x, y, 1);
   modcell(u, v, 1);
   return query();
}

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30