oj.uz

Submission #700919

# Submission time Handle Problem Language Result Execution time Memory
700919 2023-02-19T12:10:08 Z mychecksedad Seats (IOI18_seats) C++17
17 / 100
 4000 ms 127636 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;

int n, m, t[N*4][4], id[4] = {N, 0, N, 0}, A = 0;
vector<vector<int>> grid;
vector<array<int, 2>> pos;
vector<bool> is;

void build(int l, int r, int k){
  if(l == r){
    t[k][0] = pos[l - 1][0];
    t[k][1] = pos[l - 1][0];
    t[k][2] = pos[l - 1][1];
    t[k][3] = pos[l - 1][1];
    return;
  }
  int mid = l+r>>1;
  build(l, mid, k<<1);
  build(mid+1, r, k<<1|1);
  t[k][0] = min(t[k<<1][0], t[k<<1|1][0]);
  t[k][1] = max(t[k<<1][1], t[k<<1|1][1]);
  t[k][2] = min(t[k<<1][2], t[k<<1|1][2]);
  t[k][3] = max(t[k<<1][3], t[k<<1|1][3]);
}

void update(int l, int r, int p, int k){
  if(l == r){
    t[k][0] = pos[p - 1][0];
    t[k][1] = pos[p - 1][0];
    t[k][2] = pos[p - 1][1];
    t[k][3] = pos[p - 1][1];
    return;
  }
  int mid = l+r>>1;
  
  if(mid >= p)
    update(l, mid, p, k<<1);
  else
    update(mid + 1, r, p, k<<1|1);

  t[k][0] = min(t[k<<1][0], t[k<<1|1][0]);
  t[k][1] = max(t[k<<1][1], t[k<<1|1][1]);
  t[k][2] = min(t[k<<1][2], t[k<<1|1][2]);
  t[k][3] = max(t[k<<1][3], t[k<<1|1][3]);
}

int get(int l, int r, int ql, int qr, int k, int s){
  if(ql > r || qr < l) return id[s];
  if(ql <= l && r <= qr) return t[k][s];
  int mid = l+r>>1;
  int al = get(l, mid, ql, qr, k<<1, s);
  int ar = get(mid + 1, r, ql, qr, k<<1|1, s);
  return (s % 2 ? max(al, ar) : min(al, ar));
}

int calc(){
  int ans = 0;
  int u = n, d = 0, l = m, r = 0;
  for(int i = 0; i < n*m; ++i){
    u = min(u, pos[i][0]);
    d = max(d, pos[i][0]);
    l = min(l, pos[i][1]);
    r = max(r, pos[i][1]);
    if((r - l + 1) * (d - u + 1) == i + 1){
      ans++;
      is[i] = 1;
    }
  }
  return ans;
}
void calc2(int a, int b){
  int u = get(1, n*m, 1, a, 1, 0);
  int d = get(1, n*m, 1, a, 1, 1);
  int l = get(1, n*m, 1, a, 1, 2);
  int r = get(1, n*m, 1, a, 1, 3);
 
  for(int i = a - 1; i <= b - 1; ++i){
    u = min(u, pos[i][0]);
    d = max(d, pos[i][0]);
    l = min(l, pos[i][1]);
    r = max(r, pos[i][1]);
    if((r - l + 1) * (d - u + 1) == i + 1){
      if(!is[i]) A++;
      is[i] = 1;
    }else{
      if(is[i]) A--;
      is[i] = 0;
    }
  }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
  n = H, m = W;
  grid.resize(n, vector<int> (m, 0));
  is.resize(n*m);
  pos.resize(n*m);
  for(int i = 0; i < n*m; ++i) grid[R[i]][C[i]] = i, pos[i] = {R[i], C[i]};
  build(1, n*m, 1);
  A = calc();
}
int swap_seats(int a, int b){
  if(a > b) swap(a, b);
  if(b-a <= 10000){
    swap(pos[a], pos[b]);
    update(1, n*m, a + 1, 1);
    update(1, n*m, b + 1, 1);
    calc2(a + 1, b + 1);
    return A;
  }
  swap(pos[a], pos[b]);
  grid[pos[a][0]][pos[a][1]] = a;
  grid[pos[b][0]][pos[b][1]] = b;
  return calc();
}

Compilation message

seats.cpp: In function 'void build(int, int, int)':
seats.cpp:18:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |   int mid = l+r>>1;
      |             ~^~
seats.cpp: In function 'void update(int, int, int, int)':
seats.cpp:35:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid = l+r>>1;
      |             ~^~
seats.cpp: In function 'int get(int, int, int, int, int, int)':
seats.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |   int mid = l+r>>1;
      |             ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 4 ms 404 KB Output is correct
11 Correct 5 ms 340 KB Output is correct
12 Correct 5 ms 340 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 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 4 ms 404 KB Output is correct
11 Correct 5 ms 340 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 69 ms 1124 KB Output is correct
14 Correct 70 ms 1116 KB Output is correct
15 Correct 65 ms 1152 KB Output is correct
16 Correct 70 ms 1648 KB Output is correct
17 Correct 67 ms 1132 KB Output is correct
18 Correct 65 ms 1124 KB Output is correct
19 Correct 69 ms 1108 KB Output is correct
20 Correct 65 ms 1364 KB Output is correct
21 Correct 70 ms 1152 KB Output is correct
22 Correct 70 ms 1636 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 1128 KB Output is correct
2 Correct 114 ms 6908 KB Output is correct
3 Correct 328 ms 60732 KB Output is correct
4 Correct 339 ms 60748 KB Output is correct
5 Correct 366 ms 60668 KB Output is correct
6 Correct 478 ms 127636 KB Output is correct
7 Correct 357 ms 76688 KB Output is correct
8 Correct 345 ms 76740 KB Output is correct
9 Correct 345 ms 77132 KB Output is correct
10 Correct 343 ms 79800 KB Output is correct
11 Correct 381 ms 100128 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1340 KB Output is correct
2 Correct 23 ms 1332 KB Output is correct
3 Correct 36 ms 1360 KB Output is correct
4 Correct 99 ms 1312 KB Output is correct
5 Correct 635 ms 2156 KB Output is correct
6 Execution timed out 4073 ms 61048 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 3 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 4 ms 340 KB Output is correct
9 Correct 4 ms 340 KB Output is correct
10 Correct 4 ms 404 KB Output is correct
11 Correct 5 ms 340 KB Output is correct
12 Correct 5 ms 340 KB Output is correct
13 Correct 69 ms 1124 KB Output is correct
14 Correct 70 ms 1116 KB Output is correct
15 Correct 65 ms 1152 KB Output is correct
16 Correct 70 ms 1648 KB Output is correct
17 Correct 67 ms 1132 KB Output is correct
18 Correct 65 ms 1124 KB Output is correct
19 Correct 69 ms 1108 KB Output is correct
20 Correct 65 ms 1364 KB Output is correct
21 Correct 70 ms 1152 KB Output is correct
22 Correct 70 ms 1636 KB Output is correct
23 Execution timed out 4074 ms 60860 KB Time limit exceeded
24 Halted 0 ms 0 KB -