Submission #758332

#	Time	Username	Problem	Language	Result	Execution time	Memory
758332		alexander707070	Seats (IOI18_seats)	C++14	25 / 100	4064 ms	227792 KiB

seats

#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;

struct event{
    int id,val,type;

    inline friend bool operator < (event fr,event sc){
        return fr.id<sc.id;
    }
};

int n,m,minx,maxx,miny,maxy,ans,pt;
pair<int,int> w[MAXN];

set<int> row[MAXN],col[MAXN];
vector<int> curr;
vector<event> special;

void add_positions(){
    special.clear();

    curr={};
    for(int i=0;i<n;i++){
        while(!curr.empty() and *row[i].begin()<*row[curr.back()].begin()){
            curr.pop_back();
        }
        curr.push_back(i);
    }

    for(int i:curr)special.push_back({*row[i].begin(),i,1});

    curr={};
    for(int i=n-1;i>=0;i--){
        while(!curr.empty() and *row[i].begin()<*row[curr.back()].begin()){
            curr.pop_back();
        }
        curr.push_back(i);
    }

    for(int i:curr)special.push_back({*row[i].begin(),i,1});

    curr={};
    for(int i=0;i<m;i++){
        while(!curr.empty() and *col[i].begin()<*col[curr.back()].begin()){
            curr.pop_back();
        }
        curr.push_back(i);
    }
    for(int i:curr)special.push_back({*col[i].begin(),i,2});

    curr={};
    for(int i=m-1;i>=0;i--){
        while(!curr.empty() and *col[i].begin()<*col[curr.back()].begin()){
            curr.pop_back();
        }
        curr.push_back(i);
    }
    for(int i:curr)special.push_back({*col[i].begin(),i,2});

    sort(special.begin(),special.end());
}

int swap_seats(int x,int y){
    x++; y++;
    row[w[x].first].erase(x);
    col[w[x].second].erase(x);
    row[w[y].first].erase(y);
    col[w[y].second].erase(y);

    swap(w[x],w[y]);
    row[w[x].first].insert(x);
    col[w[x].second].insert(x);
    row[w[y].first].insert(y);
    col[w[y].second].insert(y);

    add_positions(); ans=0;
    special.push_back({n*m+1,0,0});
    minx=miny=n+m; maxx=maxy=-1;

    for(int i=0;i<special.size()-1;i++){
        if(special[i].type==1){
            minx=min(minx,special[i].val);
            maxx=max(maxx,special[i].val);
        }else{
            miny=min(miny,special[i].val);
            maxy=max(maxy,special[i].val);
        }

        if(special[i].id==special[i+1].id)continue;
        if((maxx-minx+1)*(maxy-miny+1)>=special[i].id and (maxx-minx+1)*(maxy-miny+1)<special[i+1].id){
            ans++;
        }
    }

    return ans;
}

void give_initial_chart(int H, int W,vector<int> R,vector<int> C){
    n=H; m=W;
    for(int i=1;i<=n*m;i++){
        w[i]={R[i-1],C[i-1]};
        row[w[i].first].insert(i);
        col[w[i].second].insert(i);
    }
}

/*
int main(){

    give_initial_chart(2, 3, {0, 1, 1, 0, 0, 1}, {0, 0, 1,1, 2, 2});
    cout<<swap_seats(0, 5)<<"\n"<<swap_seats(0, 5)<<"\n";
}
*/

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:81:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i=0;i<special.size()-1;i++){
      |                 ~^~~~~~~~~~~~~~~~~

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