Submission #79836

#	Time	Username	Problem	Language	Result	Execution time	Memory
79836		Milki	Seats (IOI18_seats)	C++14	100 / 100	2274 ms	135544 KiB

seats

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((long long) x.size())
#define pb(x) push_back(x)

typedef long long ll;
typedef pair<int, int> point;

namespace {

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

}  // namespace

const int off = 1 << 21;
const int MAXN = 1e6 + 5;
const int INF = 1e9;
int kraj;

struct Tournament{
    point t[2 * off];
    int p[2 * off];

    Tournament(){
        REP(i, 2 * off)
            t[i] = point(INF, 0);
    }
    void build(){
        for(int i = off - 1; i > 0; --i)
            t[i] = merge(t[i * 2], t[i * 2 + 1]);
    }
    void add(int x, int val){
        t[x + off] = point(val, 1);
    }
    void prop(int x){
        t[x].first += p[x];
        if(x < off){
            p[x * 2] += p[x];
            p[x * 2 + 1] += p[x];
        }
        p[x] = 0;
    }
    point merge(point a, point b){
        point ret = point(min(a.first, b.first), 0);
        if(a.first == ret.first) ret.second += a.second;
        if(b.first == ret.first) ret.second += b.second;
        return ret;
    }
    void update(int x, int lo, int hi, int a, int b, int val){
        if(a >= b) return;

        if(lo >= a && hi <= b){
            p[x] += val;
            prop(x);
            return;
        }
        prop(x);
        if(lo >= b || hi <= a) return;

        int mid = (lo + hi) >> 1;
        update(x * 2, lo, mid, a, b, val);
        update(x * 2 + 1, mid, hi, a, b, val);

        t[x] = merge(t[x * 2], t[x * 2 + 1]);
    }
    point get(int x, int lo, int hi, int a, int b){
        prop(x);
        if(lo >= a && hi <= b) return t[x];
        if(lo >= b || hi <= a) return point(-1, -1);

        int mid = (lo + hi) >> 1;
        point A = get(x * 2, lo, mid, a, b);
        point B = get(x * 2 + 1, mid, hi, a, b);

        return merge(A, B);
    }
} T;

const int dx[4][3] = { {0, -1, -1}, {-1, -1, 0}, {0, 1, 1}, {1, 1, 0} };
const int dy[4][3] = { {-1, -1, 0}, {0, 1, 1}, {1, 1, 0}, {0, -1, -1} };

vector <int> v[MAXN];

int prefix_update(int x, int y){
    int old_val = 0, val = 0;
    REP(i, 4){
        int cnt = 0;
        REP(j, 3){
            int nx = x + dx[i][j];
            int ny = y + dy[i][j];
            if(v[nx][ny] < v[x][y]) cnt ++;
        }
        if(cnt == 1 || cnt == 3) old_val ++;
    }
    REP(i, 4){
        int cnt = 0;
        REP(j, 3){
            int nx = x + dx[i][j];
            int ny = y + dy[i][j];
            if(v[nx][ny] < v[x][y]) cnt ++;
        }
        if(cnt == 0 || cnt == 2) val ++;
    }
    return val - old_val;
}

vector <int> row, col;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
    REP(i, H + 2){
        v[i].reserve(W + 2);
    }

    REP(i, H + 2)
        v[i][0] = v[i][W + 1] = INF;
    REP(i, W + 2)
        v[0][i] = v[H + 1][i] = INF;

    REP(i, H + 2)
        REP(j, W + 2)
            v[i][j] = INF;
    row.reserve(H * W + 1); col.reserve(H * W + 1);

    int pref = 0;
    REP(i, H * W){
        R[i] ++; C[i] ++;
        row.pb(R[i]); col.pb(C[i]);
        v[R[i]][C[i]] = i;
        pref += prefix_update(R[i], C[i]);
        T.add(i, pref);
    }
    T.build();
    kraj = H * W;
}

void update(int x, int y, int val){
    REP(i, 4){
        vector <int> tmp;
        REP(j, 3){
            int nx = x + dx[i][j];
            int ny = y + dy[i][j];
            tmp.pb(v[nx][ny]);
        }
        tmp.pb(v[x][y]);
        sort(tmp.begin(), tmp.end());
        REP(j, 4)
            if(tmp[j] == INF)
                tmp[j] = kraj;

        assert(v[x][y] != INF);
        if(tmp[0] == v[x][y]){
            T.update(1, 0, off, tmp[0], tmp[1], val);
            T.update(1, 0, off, tmp[1], tmp[2], -val);
            T.update(1, 0, off, tmp[2], tmp[3], val);
            T.update(1, 0, off, tmp[3], kraj, -val);
        }
        else if(tmp[1] == v[x][y]){
            T.update(1, 0, off, tmp[1], tmp[2], -val);
            T.update(1, 0, off, tmp[2], tmp[3], val);
            T.update(1, 0, off, tmp[3], kraj, -val);
        }
        else if(tmp[2] == v[x][y]){
            T.update(1, 0, off, tmp[2], tmp[3], val);
            T.update(1, 0, off, tmp[3], kraj, -val);
        }
        else if(tmp[3] == v[x][y]){
            T.update(1, 0, off, tmp[3], kraj, -val);
        }
        /*else if(tmp[1] == v[x][y] && tmp[2] != INF)
            T.update(1, 0, off, tmp[1], tmp[2], -val);
        else if(tmp[1] == v[x][y] && tmp[2] == INF)
            T.update(1, 0, off, tmp[1], kraj, -val);
        */
    }
}

int swap_seats(int a, int b){
    int x1, y1, x2, y2;
    x1 = row[a], y1 = col[a];
    x2 = row[b], y2 = col[b];

    update(x1, y1, -1);
    update(x2, y2, -1);
    swap(v[x1][y1], v[x2][y2]);
    swap(row[a], row[b]);
    swap(col[a], col[b]);
    update(x1, y1, 1);
    update(x2, y2, 1);

    return T.get(1, 0, off, 0, off).second;
}

/*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;
} */

Compilation message (stderr)

seats.cpp:15:5: warning: 'int {anonymous}::read_int()' defined but not used [-Wunused-function]
 int read_int() {
     ^~~~~~~~

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