Submission #116209

#	Time	Username	Problem	Language	Result	Execution time	Memory
116209		mirbek01	Seats (IOI18_seats)	C++11	17 / 100	4054 ms	55416 KiB

seats

# include <bits/stdc++.h>
# include "seats.h"

using namespace std;

const int N = 1e6 + 2;

int mnx[N], mny[N], mxx[N], mxy[N], ans;
vector <int> R, C;

bool check(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;
      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]);
            }
            ans += check(i);
      }
}

int swap_seats(int a, int b) {
      if(a > b)
            swap(a, b);
      for(int i = a; i <= b; i ++)
            ans -= check(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]);
            }
            ans += check(i);
      }
      return ans;
}

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 0 / 20
• Subtask 4: 6 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30