Submission #769264

#	Time	Username	Problem	Language	Result	Execution time	Memory
769264		Alihan_8	Seats (IOI18_seats)	C++17	0 / 100	4065 ms	35760 KiB

seats

#include <bits/stdc++.h>

//#include "seats.h"

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
//#define int long long

template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}

template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag = false;
    if ( x < y ){
        x = y; flag |= true;
    }
    return flag;
}

const int inf = 1e9 + 1;

struct MinSegTree{
    vector <int> T;
    int N;
    void fix(vector <int> p){
        int n = (int)p.size();
        N = n;
        T.resize(n * 4 + 1);
        function <void(int,int,int)> build = [&](int v, int l, int r){
            if ( l == r ){
                T[v] = p[l];
                return;
            }
            int md = (l + r) >> 1;
            build(v * 2, l, md), build(v * 2 + 1, md + 1, r);
            T[v] = min(T[v * 2], T[v * 2 + 1]);
        }; build(1, 0, N - 1);
    }
    void upd(int v, int l, int r, int pos, int val){
        if ( l == r ){
            T[v] = val;
            return;
        }
        int md = (l + r) >> 1;
        if ( pos <= md ){
            upd(v * 2, l, md, pos, val);
        } else{
            upd(v * 2 + 1, md + 1, r, pos, val);
        }
        T[v] = min(T[v * 2], T[v * 2 + 1]);
    }
    int get(int v, int l, int r, int tl, int tr){
        if ( l > tr or r < tl ){
            return inf;
        }
        if ( tl <= l and tr >= r ){
            return T[v];
        }
        int md = (l + r) >> 1;
        return min(get(v * 2, l, md, tl, tr), get(v * 2 + 1, md + 1, r, tl, tr));
    }
    void upd(int pos, int val){ upd(1, 0, N - 1, pos, val); }
    int get(int l, int r){ return get(1, 0, N - 1, l, r); }
};

vector <MinSegTree> T;

int h, w;

vector <vector<int>> p;

vector <int> r, c;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    swap(r, R), swap(c, C);
    h = H, w = W;
    T.resize(h); p.resize(h);
    for ( auto &v: p ) v.resize(w);
    for ( int i = 0; i < h * w; i++ ){
        p[r[i]][c[i]] = i;
    }
    for ( int i = 0; i < h; i++ ){
        T[i].fix(p[i]);
    }
}

int swap_seats(int a, int b) {
    T[r[a]].upd(c[a], b);
    T[r[b]].upd(c[b], a);
    swap(r[a], r[b]), swap(c[a], c[b]);
    swap(p[r[a]][c[a]], p[r[b]][c[b]]);
    int cnt = 1;
    for ( int i = 1; i < h * w; i++ ){
        int x = c[i], y = c[i];
        while ( x > 0 and p[r[i]][x - 1] < i ) --x;
        while ( y + 1 < w and p[r[i]][y + 1] < i ) ++y;
        int tl = r[i], tr = r[i];
        while ( tl > 0 and T[tl - 1].get(x, y) < i ) --tl;
        while ( tr + 1 < h and T[tr + 1].get(x, y) < i ) ++tr;
        cnt += ((y - x + 1) * (tr - tl + 1) == i + 1);
    }
    return cnt;
}


#ifndef EVAL
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5

ANS: {3, 4}
*/
#include <cstdio>
#include <cstdlib>
#include <vector>

namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  int H = read_int();
  int W = read_int();
  int Q = read_int();
  std::vector<int> R(H * W), C(H * W);
  for (int i = 0; i < H * W; ++i) {
    R[i] = read_int();
    C[i] = read_int();
  }
  std::vector<int> A(Q), B(Q);
  for (int j = 0; j < Q; ++j) {
    A[j] = read_int();
    B[j] = read_int();
  }

  give_initial_chart(H, W, R, C);
  for (int j = 0; j < Q; ++j) {
    int answer = swap_seats(A[j], B[j]);
    printf("%d\n", answer);
  }
  return 0;
}
#endif // EVAL

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