oj.uz

Submission #288543

# Submission time Handle Problem Language Result Execution time Memory
288543 2020-09-01T15:42:54 Z Mercenary Seats (IOI18_seats) C++14
5 / 100
 4000 ms 61176 KB 
#include "seats.h"

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;

vector<vector<int>> a;
vector<int> r , c;
int n , m;
int s[4][maxn * maxn * 4];
void update(int x , int l , int r , int pos , int& valx , int &valy){
    if(l == r){
        s[0][x] = s[1][x] = valx;
        s[2][x] = s[3][x] = valy;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid)update(x * 2 , l , mid , pos , valx , valy);
    else update(x * 2 + 1 , mid + 1 , r , pos , valx , valy);
    s[0][x] = max(s[0][x * 2] , s[0][x * 2 + 1]);
    s[1][x] = min(s[1][x * 2] , s[1][x * 2 + 1]);
    s[2][x] = max(s[2][x * 2] , s[2][x * 2 + 1]);
    s[3][x] = min(s[3][x * 2] , s[3][x * 2 + 1]);

}
void query(int x , int l , int r , int L , int R , int &lx , int &rx , int & ly , int & ry){
    if(L > r || l > R)return;
    if(L <= l && r <= R){
        lx = min(lx , s[1][x]);
        ly = min(ly , s[3][x]);
        rx = max(rx , s[0][x]);
        ry = max(ry , s[2][x]);
        return ;
    }
    int mid = l + r >> 1;
    query(x * 2 , l , mid , L , R , lx , rx , ly , ry);
    query(x * 2 + 1, mid + 1 , r , L , R , lx , rx , ly , ry);
}
void build(int x , int l , int r){
    if(l == r){
        s[0][x] = s[1][x] = ::r[l - 1];
        s[2][x] = s[3][x] = ::c[l - 1];
        return;
    }
    int mid = l + r >> 1;
    build(x * 2 , l , mid);
    build(x * 2 + 1 , mid + 1 , r);
    s[0][x] = max(s[0][x * 2] , s[0][x * 2 + 1]);
    s[1][x] = min(s[1][x * 2] , s[1][x * 2 + 1]);
    s[2][x] = max(s[2][x * 2] , s[2][x * 2 + 1]);
    s[3][x] = min(s[3][x * 2] , s[3][x * 2 + 1]);
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    r = R;c = C;
    m = H;n = W;
    a.resize(m , vector<int>(n , 0));
    for(int i = 0 ; i < n * m ; ++i)a[r[i]][c[i]] = i;
    if(n <= 1000 && m <= 1000){
        build(1,1,m*n);
    }
}

int swap_seats(int u , int v) {
    if(n <= 1000 && m <= 1000){
        update(1 , 1 , m * n , u + 1 , r[v] , c[v]);
        update(1 , 1 , m * n , v + 1 , r[u] , c[u]);
        swap(r[u] , r[v]);swap(c[u] , c[v]);
        int lx = m - 1, ly = n - 1 , rx = 0 , ry = 0;
        int res = 0;
        for(int i = 0 ; i < n * m ; ++i){
            res++;
            while(true){
                query(1,1,m*n,1,i+1,lx,rx,ly,ry);
                if(i == (rx - lx + 1) * (ry - ly + 1) - 1)break;
                i = (rx - lx + 1) * (ry - ly + 1) - 1;
            }
//            cout << endl;
        }
        return res;
    }
}

#ifdef LOCAL
#include <cstdio>
#include <cstdlib>
#include <vector>
#include "seats.h"

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() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
        freopen(taskname".INP", "r",stdin);
        freopen(taskname".OUT", "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]);
    cout << answer << endl;
  }
  return 0;
}

#endif // LOCAL

Compilation message

seats.cpp: In function 'void update(int, int, int, int, int&, int&)':
seats.cpp:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid = l + r >> 1;
      |               ~~^~~
seats.cpp: In function 'void query(int, int, int, int, int, int&, int&, int&, int&)':
seats.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = l + r >> 1;
      |               ~~^~~
seats.cpp: In function 'void build(int, int, int)':
seats.cpp:60:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int mid = l + r >> 1;
      |               ~~^~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:97:1: warning: control reaches end of non-void function [-Wreturn-type]
   97 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 37 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 9 ms 512 KB Output is correct
9 Correct 9 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 37 ms 512 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 37 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 9 ms 512 KB Output is correct
9 Correct 9 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 37 ms 512 KB Output is correct
13 Correct 13 ms 1408 KB Output is correct
14 Correct 11 ms 1408 KB Output is correct
15 Execution timed out 4051 ms 1024 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 61172 KB Output is correct
2 Correct 462 ms 61176 KB Output is correct
3 Correct 3722 ms 61176 KB Output is correct
4 Correct 597 ms 61176 KB Output is correct
5 Correct 561 ms 61068 KB Output is correct
6 Execution timed out 4038 ms 61176 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1408 KB Output is correct
2 Correct 105 ms 7416 KB Output is correct
3 Correct 3302 ms 61168 KB Output is correct
4 Correct 421 ms 61152 KB Output is correct
5 Execution timed out 4091 ms 32120 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1908 KB Output is correct
2 Correct 41 ms 2036 KB Output is correct
3 Correct 361 ms 1908 KB Output is correct
4 Correct 3665 ms 2384 KB Output is correct
5 Execution timed out 4029 ms 1792 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 640 KB Output is correct
5 Correct 37 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 512 KB Output is correct
8 Correct 9 ms 512 KB Output is correct
9 Correct 9 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 37 ms 512 KB Output is correct
13 Correct 13 ms 1408 KB Output is correct
14 Correct 11 ms 1408 KB Output is correct
15 Execution timed out 4051 ms 1024 KB Time limit exceeded
16 Halted 0 ms 0 KB -