Submission #1052614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052614		Ahmed57	Seats (IOI18_seats)	C++17	37 / 100	4058 ms	59604 KiB

seats

#include "bits/stdc++.h"

using namespace std;
vector<int> r,c;
int h,w;
int cst[1000001];
int mnx[1000001];
int mny[1000001];
int mxx[1000001];
int mxy[1000001];
int all = 0;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
    h = H;
    w = W;
    for(int i = 0;i<H*W;i++){
        r.push_back(R[i]);
        c.push_back(C[i]);
    }
    mnx[0] = 1e9;
    mny[0] = 1e9;
    mxx[0] = -1e9;
    mxy[0] = -1e9;
    for(int i = 0;i<h*w;i++){
        mnx[i+1] = min(mnx[i],r[i]);
        mxx[i+1] = max(mxx[i],r[i]);
        mny[i+1] = min(mny[i],c[i]);
        mxy[i+1] = max(mxy[i],c[i]);
        if(i+1==(mxx[i+1]-mnx[i+1]+1)*(mxy[i+1]-mny[i+1]+1)){
            cst[i] = 1;
            all++;
        }else cst[i] = 0;
    }
}
int swap_seats(int a, int b){
    if(a>b)swap(a,b);
    swap(r[a],r[b]);
    swap(c[a],c[b]);
    for(int i = a;i<b;i++){
        all-=cst[i];
        mnx[i+1] = min(mnx[i],r[i]);
        mxx[i+1] = max(mxx[i],r[i]);
        mny[i+1] = min(mny[i],c[i]);
        mxy[i+1] = max(mxy[i],c[i]);
        if(i+1==(mxx[i+1]-mnx[i+1]+1)*(mxy[i+1]-mny[i+1]+1)){
            all++;
            cst[i] = 1;
        }else cst[i] = 0;
    }
    return all;
}

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