oj.uz

Submission #129538

# Submission time Handle Problem Language Result Execution time Memory
129538 2019-07-12T13:05:13 Z Talant Seats (IOI18_seats) C++11
5 / 100
 4000 ms 60152 KB 
    # include <bits/stdc++.h>
    # include "seats.h"
     
    using namespace std;
     
    const int N = 1e6 + 2;
     
    int t[4][N * 4];
    int mnx[N], mny[N], mxx[N], mxy[N], rt, h, w;
    vector <int> R, C;
     
    void upd(int pos, int v = 1, int tl = 1, int tr = R.size()){
          if(tl == tr){
                t[0][v] = R[tl - 1];
                t[1][v] = C[tl - 1];
                t[2][v] = R[tl - 1];
                t[3][v] = C[tl - 1];
          } else {
                int tm = (tl + tr) >> 1;
                if(pos <= tm)
                      upd(pos, v << 1, tl, tm);
                else
                      upd(pos, v << 1 | 1, tm + 1, tr);
                t[0][v] = max(t[0][v << 1], t[0][v << 1 | 1]);
                t[1][v] = max(t[1][v << 1], t[1][v << 1 | 1]);
                t[2][v] = min(t[2][v << 1], t[2][v << 1 | 1]);
                t[3][v] = min(t[3][v << 1], t[3][v << 1 | 1]);
          }
    }
     
    pair < pair <int, int>, pair <int, int> > get(int l, int r, int v = 1, int tl = 1, int tr = R.size()){
          if(l > tr || tl > r){
                return {{0, 0}, {1e9, 1e9}};
          }
          if(l <= tl && tr <= r)
                return {{t[0][v], t[1][v]}, {t[2][v], t[3][v]}};
          int tm = (tl + tr) >> 1;
          pair < pair <int, int>, pair <int, int> > L, R;
          L = get(l, r, v << 1, tl, tm);
          R = get(l, r, v << 1 | 1, tm + 1, tr);
          L.first.first = max(L.first.first, R.first.first);
          L.first.second = max(L.first.second, R.first.second);
          L.second.first = min(L.second.first, R.second.first);
          L.second.second = min(L.second.second, R.second.second);
          return L;
    }
     
    int check(int x){
          pair < pair <int, int>, pair <int, int> > g = get(1, x);
          int ret = (g.first.first - g.second.first + 1) * (g.first.second - g.second.second + 1);
          return ret;
    }
     
    void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
          R = r, C = c;
          h = H, w = W;
      for(int i = 0; i < R.size(); i ++)
        upd(i + 1);
                
       
    }
     
    int swap_seats(int a, int b) {
                if(a > b)
                      swap(a, b);
     
                swap(R[a], R[b]);
                swap(C[a], C[b]);
     
                upd(a + 1);
                upd(b + 1);
     
                int ans = 1, cur = 1;
     
                while(cur < R.size()){
                      int ret = check(cur + 1);
                      if(ret == cur + 1){
                            cur ++, ans ++;
                      } else {
                            cur = ret - 1;
                      }
                }
     
                return ans;

    }

Compilation message

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:57:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < R.size(); i ++)
                      ~~^~~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:75:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(cur < R.size()){
                       ~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 31 ms 604 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 9 ms 512 KB Output is correct
9 Correct 9 ms 508 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 32 ms 504 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 31 ms 604 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 9 ms 512 KB Output is correct
9 Correct 9 ms 508 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 32 ms 504 KB Output is correct
13 Correct 15 ms 1400 KB Output is correct
14 Correct 12 ms 1272 KB Output is correct
15 Correct 12 ms 1272 KB Output is correct
16 Execution timed out 4013 ms 1272 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 60040 KB Output is correct
2 Correct 599 ms 60076 KB Output is correct
3 Execution timed out 4094 ms 60088 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1400 KB Output is correct
2 Correct 113 ms 7900 KB Output is correct
3 Correct 3758 ms 60024 KB Output is correct
4 Correct 546 ms 60096 KB Output is correct
5 Execution timed out 4026 ms 60152 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2136 KB Output is correct
2 Correct 33 ms 2036 KB Output is correct
3 Correct 291 ms 2252 KB Output is correct
4 Correct 3306 ms 2012 KB Output is correct
5 Correct 75 ms 2284 KB Output is correct
6 Correct 3086 ms 57100 KB Output is correct
7 Correct 2834 ms 57136 KB Output is correct
8 Correct 2579 ms 57228 KB Output is correct
9 Correct 683 ms 57128 KB Output is correct
10 Execution timed out 4094 ms 57204 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 7 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 31 ms 604 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 9 ms 512 KB Output is correct
9 Correct 9 ms 508 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 6 ms 504 KB Output is correct
12 Correct 32 ms 504 KB Output is correct
13 Correct 15 ms 1400 KB Output is correct
14 Correct 12 ms 1272 KB Output is correct
15 Correct 12 ms 1272 KB Output is correct
16 Execution timed out 4013 ms 1272 KB Time limit exceeded
17 Halted 0 ms 0 KB -