oj.uz

Submission #769270

# Submission time Handle Problem Language Result Execution time Memory
769270 2023-06-29T11:15:42 Z Alihan_8 Seats (IOI18_seats) C++17
11 / 100
 4000 ms 56364 KB 
#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 x = inf, y = -inf, tl = inf, tr = -inf, cnt = 0;
    for ( int i = 0; i < h * w; i++ ){
        chmin(x, r[i]), chmax(y, r[i]);
        chmin(tl, c[i]), chmax(tr, c[i]);
        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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Correct 3 ms 392 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 440 KB Output is correct
10 Correct 3 ms 412 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Correct 3 ms 392 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 440 KB Output is correct
10 Correct 3 ms 412 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 123 ms 872 KB Output is correct
14 Correct 140 ms 908 KB Output is correct
15 Correct 121 ms 908 KB Output is correct
16 Correct 122 ms 1856 KB Output is correct
17 Correct 121 ms 884 KB Output is correct
18 Correct 120 ms 864 KB Output is correct
19 Correct 130 ms 956 KB Output is correct
20 Correct 121 ms 1372 KB Output is correct
21 Correct 121 ms 912 KB Output is correct
22 Correct 134 ms 1876 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4006 ms 35780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 704 KB Output is correct
2 Correct 1091 ms 4188 KB Output is correct
3 Execution timed out 4104 ms 36620 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1360 KB Output is correct
2 Correct 15 ms 1376 KB Output is correct
3 Correct 28 ms 1452 KB Output is correct
4 Correct 138 ms 1392 KB Output is correct
5 Correct 1228 ms 2408 KB Output is correct
6 Execution timed out 4035 ms 56364 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 436 KB Output is correct
5 Correct 3 ms 392 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 3 ms 440 KB Output is correct
10 Correct 3 ms 412 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 123 ms 872 KB Output is correct
14 Correct 140 ms 908 KB Output is correct
15 Correct 121 ms 908 KB Output is correct
16 Correct 122 ms 1856 KB Output is correct
17 Correct 121 ms 884 KB Output is correct
18 Correct 120 ms 864 KB Output is correct
19 Correct 130 ms 956 KB Output is correct
20 Correct 121 ms 1372 KB Output is correct
21 Correct 121 ms 912 KB Output is correct
22 Correct 134 ms 1876 KB Output is correct
23 Execution timed out 4006 ms 35780 KB Time limit exceeded
24 Halted 0 ms 0 KB -