Submission #288625

#	Time	Username	Problem	Language	Result	Execution time	Memory
288625		dandrozavr	Seats (IOI18_seats)	C++14	17 / 100	4099 ms	47736 KiB

seats

/*
Uruchamiamy samolot zwiadowczy ( + 500% do wzlamaniej )

/▄/  /█/  /◐/  /▐/   /▌/ /▀/ /░/ /  / choose your own style!

***IT'S OUR LONG WAY TO THE OIILLLL***


░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀  ░░░░░░░░███░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░█▌░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▀██████████████████████████████████████████████████
░░░░░░░░░░░░░░░░░░░░░░░░░░▄▄▄████▄████████ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █████
░░░░░░░░░░░░░░░░░░░░░░░░░░░▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█████████▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░◐◐◐█████████▀▀▀▀▀▀  ░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████░░░░░░░░░░░░░░░
*/
//#pragma GCC target("avx2")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")

//#include <bits/stdc++.h>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <iostream>
using namespace std;
//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;template <typename T> using ordered_set = tree <T, null_type, less< T >, rb_tree_tag,tree_order_statistics_node_update>;
//namespace fastio {template <class T> ostream &operator<<(ostream &os, const vector<T> &container) {for (auto &u : container)os << u << " ";return os;} template<class T1, class T2> ostream& operator << (ostream& os, const pair<T1, T2>& p) {return os << p.first << " " << p.second;}template <class T> ostream &operator<<(ostream &os, set<T> const& con) {    for (auto &u : con)        os << u << " ";return os;} void pr() {} template <typename T, typename... args> void pr(T x, args... tail) {cout << x << " ";pr(tail...);}} using namespace fastio;
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define F first
#define S second
#define pii pair < int , int >
#define _ <<" "<<
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
//#include "combo.h"



constexpr int MAX_N = 2000;
constexpr int MAX_NUM_MOVES = 8000;

const int N = 1000008;
int X1[N], X2[N], Y1[N], Y2[N], ans[N], all, t[N], byl[N];
vector < int > R, C;

void add(int pos, int val){
    pos += 2;
    for (; pos < N; pos += pos & -pos)
        t[pos] += val;
}

int solve(int pos){
    pos += 2;
    int ans = 0;
    for (; pos > 0; pos -= pos & -pos)
        ans += t[pos];
    return ans;
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    ::R = R;
    ::C = C;
    int n = H;
    int m = W;
//    int a[n][m];
    int x1, x2;
    x1 = x2 = R[0];
    int y1, y2;
    y1 = y2 = C[0];
    all = C.size();
    for (int i = 0; i < C.size(); ++i){
//        a[R[i]][C[i]] = i;
        x1 = min(x1, R[i]);
        y1 = min(y1, C[i]);
        x2 = max(x2, R[i]);
        y2 = max(y2, C[i]);
//        if (i)
//            ans[i] += ans[i - 1];
        if ((x2 - x1 + 1) * (y2 - y1 + 1) == i + 1) add(i, 1), byl[i] = 1;
        X1[i] = x1;
        X2[i] = x2;
        Y1[i] = y1;
        Y2[i] = y2;
//        mp[x1][{y, {x2, y2}}]
//        cout << x1 _ y1 _ x2 _ y2 << endl;
    }
}

int swap_seats(int a, int b){
    if (a == b) return ans[all];
    if (a > b) swap(a, b);
    swap(R[a], R[b]);
    swap(C[a], C[b]);
    int suf = ans[all] - ans[b];
    int x1 = 2e9, x2 = -2e9, y1 = 2e9, y2 = -2e9;
    if (a){
        x1 = X1[a - 1];
        x2 = X2[a - 1];
        y1 = Y1[a - 1];
        y2 = Y2[a - 1];
    }
    int now = 0;
    if (a) now = solve(a - 1);
//    cout << x1 _ y1 _ x2 _ y2 << endl;
//    cout << solve(all) << endl;
    for (int i = a; i < b; ++i){
        x1 = min(x1, R[i]);
        x2 = max(x2, R[i]);
        y1 = min(y1, C[i]);
        y2 = max(y2, C[i]);
//        cout << x1 _ y1 _ x2 _ y2 << endl;
//        cout << byl[i] _ solve(i) << " : ";
//        cout << byl[i] _ solve(i) << endl;
        if (byl[i]){
            add(i, -1);
            byl[i] = 0;
        }
        if ((x2 - x1 + 1) * (y2 - y1 + 1) == i + 1 && !byl[i]) byl[i] = 1, add(i, 1);
        if (x1 == X1[i] && y1 == Y1[i] && x2 == X2[i] && y2 == Y2[i]){
            break;
        }
        X1[i] = x1;
        X2[i] = x2;
        Y1[i] = y1;
        Y2[i] = y2;
    }
    return solve(all);
}

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

int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  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

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < C.size(); ++i){
      |                     ~~^~~~~~~~~~
seats.cpp:86:9: warning: unused variable 'n' [-Wunused-variable]
   86 |     int n = H;
      |         ^
seats.cpp:87:9: warning: unused variable 'm' [-Wunused-variable]
   87 |     int m = W;
      |         ^
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:117:9: warning: unused variable 'suf' [-Wunused-variable]
  117 |     int suf = ans[all] - ans[b];
      |         ^~~
seats.cpp:125:9: warning: variable 'now' set but not used [-Wunused-but-set-variable]
  125 |     int now = 0;
      |         ^~~

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