Submission #129543

#	Time	Username	Problem	Language	Result	Execution time	Memory
129543		Talant	Seats (IOI18_seats)	C++11	17 / 100	4027 ms	56952 KiB

seats

    # 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 (stderr)

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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 6 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30