oj.uz

답안 #129543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129543 2019-07-12T13:21:11 Z Talant 자리 배치 (IOI18_seats) C++11
17 / 100
 4000 ms 56952 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;
    }
    bool chck(int x){
          int ret = (mxx[x] - mnx[x] + 1) * (mxy[x] - mny[x] + 1);
          return (x + 1) == ret;
    }
     
    void give_initial_chart(int H, int W, vector<int> r, vector<int> c) {
          R = r, C = c;
          h = H, w = W;
          if(max(H, W) <= 1000){
                for(int i = 0; i < R.size(); i ++){
                      upd(i + 1);
                }
          } else {
                for(int i = 0; i < R.size(); i ++){
                      if(!i){
                            mnx[i] = mxx[i] = C[i];
                            mny[i] = mxy[i] = R[i];
                      } else {
                            mnx[i] = min(mnx[i - 1], C[i]);
                            mny[i] = min(mny[i - 1], R[i]);
                            mxx[i] = max(mxx[i - 1], C[i]);
                            mxy[i] = max(mxy[i - 1], R[i]);
                      }
                      rt += chck(i);
                }
          }
    }
     
    int swap_seats(int a, int b) {
          if(max(h, w) <= 1000){
                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;
          } else {
                if(a > b)
                      swap(a, b);
                for(int i = a; i <= b; i ++)
                      rt -= chck(i);
     
                swap(R[a], R[b]);
                swap(C[a], C[b]);
     
                for(int i = a; i <= b; i ++){
                      if(!i){
                            mnx[i] = mxx[i] = C[i];
                            mny[i] = mxy[i] = R[i];
                      } else {
                            mnx[i] = min(mnx[i - 1], C[i]);
                            mny[i] = min(mny[i - 1], R[i]);
                            mxx[i] = max(mxx[i - 1], C[i]);
                            mxy[i] = max(mxy[i - 1], R[i]);
                      }
                      rt += chck(i);
                }
                return rt;
          }
    }

Compilation message

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:62:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int i = 0; i < R.size(); i ++){
                                ~~^~~~~~~~~~
seats.cpp:66:34: 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:94:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(cur < R.size()){
                       ~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 7 ms 508 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 31 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 9 ms 504 KB Output is correct
9 Correct 9 ms 504 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 504 KB Output is correct
12 Correct 31 ms 504 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 7 ms 508 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 31 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 9 ms 504 KB Output is correct
9 Correct 9 ms 504 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 504 KB Output is correct
12 Correct 31 ms 504 KB Output is correct
13 Correct 14 ms 1144 KB Output is correct
14 Correct 11 ms 1144 KB Output is correct
15 Correct 111 ms 824 KB Output is correct
16 Correct 110 ms 760 KB Output is correct
17 Correct 110 ms 1032 KB Output is correct
18 Correct 720 ms 1352 KB Output is correct
19 Correct 1424 ms 1268 KB Output is correct
20 Correct 115 ms 1016 KB Output is correct
21 Correct 114 ms 1016 KB Output is correct
22 Correct 116 ms 1016 KB Output is correct

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 538 ms 56752 KB Output is correct
2 Correct 577 ms 56952 KB Output is correct
3 Execution timed out 4027 ms 56824 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1144 KB Output is correct
2 Correct 112 ms 6620 KB Output is correct
3 Correct 3746 ms 56824 KB Output is correct
4 Correct 536 ms 56824 KB Output is correct
5 Correct 481 ms 39520 KB Output is correct
6 Correct 495 ms 55580 KB Output is correct
7 Correct 481 ms 55544 KB Output is correct
8 Correct 480 ms 55544 KB Output is correct
9 Correct 511 ms 55420 KB Output is correct
10 Correct 482 ms 55544 KB Output is correct
11 Correct 489 ms 55416 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 1396 KB Output is correct
2 Correct 32 ms 1396 KB Output is correct
3 Correct 291 ms 1516 KB Output is correct
4 Correct 3272 ms 1676 KB Output is correct
5 Correct 1066 ms 1912 KB Output is correct
6 Execution timed out 4018 ms 39928 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 504 KB Output is correct
2 Correct 7 ms 508 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 6 ms 504 KB Output is correct
5 Correct 31 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 9 ms 504 KB Output is correct
9 Correct 9 ms 504 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 504 KB Output is correct
12 Correct 31 ms 504 KB Output is correct
13 Correct 14 ms 1144 KB Output is correct
14 Correct 11 ms 1144 KB Output is correct
15 Correct 111 ms 824 KB Output is correct
16 Correct 110 ms 760 KB Output is correct
17 Correct 110 ms 1032 KB Output is correct
18 Correct 720 ms 1352 KB Output is correct
19 Correct 1424 ms 1268 KB Output is correct
20 Correct 115 ms 1016 KB Output is correct
21 Correct 114 ms 1016 KB Output is correct
22 Correct 116 ms 1016 KB Output is correct
23 Correct 538 ms 56752 KB Output is correct
24 Correct 577 ms 56952 KB Output is correct
25 Execution timed out 4027 ms 56824 KB Time limit exceeded
26 Halted 0 ms 0 KB -