제출 #769305

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
769305		Alihan_8	자리 배치 (IOI18_seats)	C++17	0 / 100	4078 ms	35564 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;

int h, w;

vector <int> r, c;

vector <array<int,4>> F;

struct FenwSum{
    vector <int> fenw;
    void fix(int n){
        fenw.resize(n + 1, 0);
    }
    void upd(int i, int val){ i++;
        for (; i <= (int)fenw.size(); i += i & - i ){
            fenw[i] += val;
        }
    }
    int get(int i){
        int cnt = 0; ++i;
        for (; i > 0; i -= i & -i ){
            cnt += fenw[i];
        }
        return cnt;
    }
    int get(int l, int r){ return get(r) - get(l - 1); }
} fenw;
bool g(int i){
    return ((F[i][1] - F[i][0] + 1) * (F[i][3] - F[i][2] + 1) == i + 1);
}

void upd(int i){
    F[i][0] = min(i ? F[i - 1][0] : inf, r[i]);
    F[i][1] = max(i ? F[i - 1][1] : -inf, r[i]);
    F[i][2] = min(i ? F[i - 1][2] : inf, c[i]);
    F[i][3] = max(i ? F[i - 1][3] : -inf, c[i]);
    fenw.upd(i, g(i));
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    swap(r, R), swap(c, C);
    h = H, w = W;
    F.resize(h * w); fenw.fix(h * w);
    for ( int i = 0; i < h * w; i++ ) upd(i);
}

int swap_seats(int a, int b) {
    for ( int i = a; i <= b; i++ ){
        fenw.upd(i, -g(i));
    }
    swap(r[a], r[b]), swap(c[a], c[b]);
    for ( int i = a; i <= b; i++ ) upd(i);
    return fenw.get(0, h * w - 1);
}


#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