oj.uz

Submission #292550

# Submission time Handle Problem Language Result Execution time Memory
292550 2020-09-07T09:08:23 Z oolimry Seats (IOI18_seats) C++14
100 / 100
 2588 ms 149488 KB 
#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

const long long inf = 1e9;
typedef pair<long long, int> ii;

///We want to see at each T, whether the numbers from 0 to T form a rectangle. We consider all squares from 0 to T labelled as black
///For some T, consider all 2x2 squares on the grid. A beautiful rectangle is formed if and only if:
///there are exactly 4 2x2 squares with 1 black square, and no 2x2 squares with 3 black squares.

///Let the 4 numbers in the 2x2 square be a, b, c, d where a < b < c < d.
///From T = a to T = b - 1, there is one more 2x2 square with one black square
///From T = c to T = d - 1, there is a 2x2 square with 3 black squares, hence it is impossible

///We can represent this as a segment tree for all T from 0 to HW - 1.
///For all T, the number of 2x2 squares with one black square cannot go below 4, hence it is sufficient to query if the minimum is 4, and if so, and how many 4s are there.
///We can do a range update(+1) from T = a to T = b - 1
///As for T = c to T = d - 1, we can add a very large number to indicate that we are "ruining" the range, as this range is completely impossible.

///Then for every swap, only 8 2x2 squares are affected.
///We can undo the range updates, swap the two values, and redo the range updates.


///we build a grid such that the boundaries are filled with the number n
int n, rows, cols;
static ii pos[1000005]; ///for each number, ii(r, c)
static vector<vector<int> > arr; ///arr[r*cols+c] is the element at (r,c)

///Everything here onwards is segment tree
///This is a range min range add segment tree, but we also store the no. of occurances of the minimum element
static ii tree[2000005]; ///we store the minimum element, and the number of occurances
static long long lazy[2000005]; 

///helper function to update the value of node i from the children of i
inline void relax(int i){
  if(tree[i<<1].first == tree[i<<1|1].first){
    tree[i] = ii(tree[i<<1].first+lazy[i], tree[i<<1].second + tree[i<<1|1].second);
  } 
  else{
    tree[i] = min(tree[i<<1],tree[i<<1|1]);
    tree[i].first += lazy[i];
  }
}

void initSegment(){
  for(int i = n;i < 2 * n;i++) tree[i] = ii(0,1);
  for(int i = n - 1;i >= 0;i--) relax(i);
}

inline void update(int l, int r, long long v){
  if(l == r) return;
  int ll = l + n, rr = r - 1 + n;
  for(l += n,r += n;l < r;l>>=1,r>>=1){
    if(l&1){
      tree[l].first += v;
      lazy[l] += v;
      l++;
    }
    if(r&1){
      r--;
      tree[r].first += v;
      lazy[r] += v;
    }
  }
  while(ll > 1){
    ll >>= 1;
    relax(ll);
  }
  while(rr > 1){
    rr >>= 1;
    relax(rr);
  }
}

///We need not propogate the lazy since we only query the entire range. We just store the lazy
inline int query(){
  return tree[1].second; ///the global minimum is definitely 4 (since 0 and everything form beautiful rectangles), hence just return the no. of occurances.
}

///consider a 2x2 square whose top-left corner is at r, c
void makeUpdate(int r, int c, bool isUndo){
  vector<int> values = {arr[r][c],arr[r+1][c],arr[r][c+1],arr[r+1][c+1]};
  sort(values.begin(),values.end());

  ///if isReverse, we undo our previous update
  if(isUndo){
    update(values[0],values[1],-1);
    update(values[2],values[3],-inf);
  }
  else{
    update(values[0],values[1],1); ///add one to the range, there is one more 2x2 square with exactly 1 black square
    update(values[2],values[3],inf); ///add infinity to "ruin" that range. When there are 2 black squares in the 2x2 square, it's impossible to have  beautiful rectangle
  }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
  n = H * W;
  rows = H; cols = W;
  for(int i = 0;i < rows+2;i++){
    arr.push_back({});
    arr.back().assign(cols+2,n);
  }
  for(int i = 0;i < n;i++){
    R[i]++; C[i]++;
    arr[R[i]][C[i]] = i;
    pos[i] = ii(R[i],C[i]);
  }

  initSegment();

  for(int r = 0;r <= rows;r++){
    for(int c = 0;c <= cols;c++){
      makeUpdate(r,c,false);
    }
  }	
}

int swap_seats(int a, int b) {
  ii aPos = pos[a]; ii bPos = pos[b];

  ///undo updates for all affected rectangles
  makeUpdate(aPos.first-1,aPos.second-1,true);
  makeUpdate(aPos.first,aPos.second-1,true);
  makeUpdate(aPos.first-1,aPos.second,true);
  makeUpdate(aPos.first,aPos.second,true);
  makeUpdate(bPos.first-1,bPos.second-1,true);
  makeUpdate(bPos.first,bPos.second-1,true);
  makeUpdate(bPos.first-1,bPos.second,true);
  makeUpdate(bPos.first,bPos.second,true);


  ///swapping the elements
  pos[b] = aPos; pos[a] = bPos;
  arr[aPos.first][aPos.second] = b; arr[bPos.first][bPos.second] = a;


  ///now update again for all affected rectangles
  makeUpdate(aPos.first-1,aPos.second-1,false);
  makeUpdate(aPos.first,aPos.second-1,false);
  makeUpdate(aPos.first-1,aPos.second,false);
  makeUpdate(aPos.first,aPos.second,false);
  makeUpdate(bPos.first-1,bPos.second-1,false);
  makeUpdate(bPos.first,bPos.second-1,false);
  makeUpdate(bPos.first-1,bPos.second,false);
  makeUpdate(bPos.first,bPos.second,false);

  return query();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 512 KB Output is correct
2 Correct 18 ms 512 KB Output is correct
3 Correct 24 ms 512 KB Output is correct
4 Correct 17 ms 512 KB Output is correct
5 Correct 15 ms 512 KB Output is correct
6 Correct 22 ms 512 KB Output is correct
7 Correct 22 ms 512 KB Output is correct
8 Correct 22 ms 512 KB Output is correct
9 Correct 22 ms 512 KB Output is correct
10 Correct 22 ms 512 KB Output is correct
11 Correct 21 ms 512 KB Output is correct
12 Correct 16 ms 512 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 512 KB Output is correct
2 Correct 18 ms 512 KB Output is correct
3 Correct 24 ms 512 KB Output is correct
4 Correct 17 ms 512 KB Output is correct
5 Correct 15 ms 512 KB Output is correct
6 Correct 22 ms 512 KB Output is correct
7 Correct 22 ms 512 KB Output is correct
8 Correct 22 ms 512 KB Output is correct
9 Correct 22 ms 512 KB Output is correct
10 Correct 22 ms 512 KB Output is correct
11 Correct 21 ms 512 KB Output is correct
12 Correct 16 ms 512 KB Output is correct
13 Correct 46 ms 1380 KB Output is correct
14 Correct 55 ms 1400 KB Output is correct
15 Correct 36 ms 1408 KB Output is correct
16 Correct 31 ms 1884 KB Output is correct
17 Correct 44 ms 1408 KB Output is correct
18 Correct 47 ms 1400 KB Output is correct
19 Correct 44 ms 1416 KB Output is correct
20 Correct 39 ms 1664 KB Output is correct
21 Correct 31 ms 1408 KB Output is correct
22 Correct 32 ms 1852 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1771 ms 82728 KB Output is correct
2 Correct 1054 ms 98680 KB Output is correct
3 Correct 979 ms 97272 KB Output is correct
4 Correct 859 ms 98568 KB Output is correct
5 Correct 897 ms 98680 KB Output is correct
6 Correct 977 ms 98680 KB Output is correct
7 Correct 963 ms 98552 KB Output is correct
8 Correct 920 ms 98572 KB Output is correct
9 Correct 954 ms 98680 KB Output is correct
10 Correct 949 ms 98168 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1536 KB Output is correct
2 Correct 133 ms 8136 KB Output is correct
3 Correct 879 ms 83064 KB Output is correct
4 Correct 1783 ms 83244 KB Output is correct
5 Correct 961 ms 98800 KB Output is correct
6 Correct 1891 ms 149488 KB Output is correct
7 Correct 882 ms 99468 KB Output is correct
8 Correct 1046 ms 98808 KB Output is correct
9 Correct 1014 ms 93364 KB Output is correct
10 Correct 1022 ms 103356 KB Output is correct
11 Correct 980 ms 120332 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 2036 KB Output is correct
2 Correct 119 ms 2036 KB Output is correct
3 Correct 153 ms 2036 KB Output is correct
4 Correct 196 ms 2164 KB Output is correct
5 Correct 271 ms 3060 KB Output is correct
6 Correct 1268 ms 87032 KB Output is correct
7 Correct 1420 ms 90892 KB Output is correct
8 Correct 1269 ms 83940 KB Output is correct
9 Correct 2295 ms 90820 KB Output is correct
10 Correct 1272 ms 103432 KB Output is correct
11 Correct 1300 ms 105588 KB Output is correct
12 Correct 1277 ms 100324 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 512 KB Output is correct
2 Correct 18 ms 512 KB Output is correct
3 Correct 24 ms 512 KB Output is correct
4 Correct 17 ms 512 KB Output is correct
5 Correct 15 ms 512 KB Output is correct
6 Correct 22 ms 512 KB Output is correct
7 Correct 22 ms 512 KB Output is correct
8 Correct 22 ms 512 KB Output is correct
9 Correct 22 ms 512 KB Output is correct
10 Correct 22 ms 512 KB Output is correct
11 Correct 21 ms 512 KB Output is correct
12 Correct 16 ms 512 KB Output is correct
13 Correct 46 ms 1380 KB Output is correct
14 Correct 55 ms 1400 KB Output is correct
15 Correct 36 ms 1408 KB Output is correct
16 Correct 31 ms 1884 KB Output is correct
17 Correct 44 ms 1408 KB Output is correct
18 Correct 47 ms 1400 KB Output is correct
19 Correct 44 ms 1416 KB Output is correct
20 Correct 39 ms 1664 KB Output is correct
21 Correct 31 ms 1408 KB Output is correct
22 Correct 32 ms 1852 KB Output is correct
23 Correct 1771 ms 82728 KB Output is correct
24 Correct 1054 ms 98680 KB Output is correct
25 Correct 979 ms 97272 KB Output is correct
26 Correct 859 ms 98568 KB Output is correct
27 Correct 897 ms 98680 KB Output is correct
28 Correct 977 ms 98680 KB Output is correct
29 Correct 963 ms 98552 KB Output is correct
30 Correct 920 ms 98572 KB Output is correct
31 Correct 954 ms 98680 KB Output is correct
32 Correct 949 ms 98168 KB Output is correct
33 Correct 46 ms 1536 KB Output is correct
34 Correct 133 ms 8136 KB Output is correct
35 Correct 879 ms 83064 KB Output is correct
36 Correct 1783 ms 83244 KB Output is correct
37 Correct 961 ms 98800 KB Output is correct
38 Correct 1891 ms 149488 KB Output is correct
39 Correct 882 ms 99468 KB Output is correct
40 Correct 1046 ms 98808 KB Output is correct
41 Correct 1014 ms 93364 KB Output is correct
42 Correct 1022 ms 103356 KB Output is correct
43 Correct 980 ms 120332 KB Output is correct
44 Correct 96 ms 2036 KB Output is correct
45 Correct 119 ms 2036 KB Output is correct
46 Correct 153 ms 2036 KB Output is correct
47 Correct 196 ms 2164 KB Output is correct
48 Correct 271 ms 3060 KB Output is correct
49 Correct 1268 ms 87032 KB Output is correct
50 Correct 1420 ms 90892 KB Output is correct
51 Correct 1269 ms 83940 KB Output is correct
52 Correct 2295 ms 90820 KB Output is correct
53 Correct 1272 ms 103432 KB Output is correct
54 Correct 1300 ms 105588 KB Output is correct
55 Correct 1277 ms 100324 KB Output is correct
56 Correct 140 ms 2036 KB Output is correct
57 Correct 230 ms 2036 KB Output is correct
58 Correct 409 ms 3000 KB Output is correct
59 Correct 1540 ms 99960 KB Output is correct
60 Correct 2588 ms 99692 KB Output is correct
61 Correct 1408 ms 99592 KB Output is correct
62 Correct 1383 ms 96364 KB Output is correct
63 Correct 2536 ms 102144 KB Output is correct
64 Correct 1621 ms 100364 KB Output is correct
65 Correct 1448 ms 99572 KB Output is correct
66 Correct 1704 ms 93748 KB Output is correct
67 Correct 1557 ms 104500 KB Output is correct
68 Correct 1469 ms 113032 KB Output is correct
69 Correct 2491 ms 123132 KB Output is correct