Submission #295671

#	Time	Username	Problem	Language	Result	Execution time	Memory
295671		DanerZein	Seats (IOI18_seats)	C++14	31 / 100	4100 ms	62712 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define MAX 1000000000
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii,ii> iii;
int ns;
ii val[1000010];
ii tma[4000010];
ii tmi[4000010];
void init(int node,int a,int b){
  if(a==b){
    tmi[node]=val[a];
    tma[node]=val[a];
    return;
  }
  int mid=(a+b)/2;
  init(2*node+1,a,mid);
  init(2*node+2,mid+1,b);
  tma[node].first=max(tma[2*node+1].first,tma[2*node+2].first);
  tma[node].second=max(tma[2*node+1].second,tma[2*node+2].second);
  tmi[node].first=min(tmi[2*node+1].first,tmi[2*node+2].first);
  tmi[node].second=min(tmi[2*node+1].second,tmi[2*node+2].second);
}
void update(int node,int a,int b,int id,ii va){
  if(a>id or id>b) return;
  if(a==b and a==id){
    tma[node]=va;
    tmi[node]=va;
    return;
  }
  int le=2*node+1,ri=2*node+2,mid=(a+b)/2;
  update(le,a,mid,id,va);
  update(ri,mid+1,b,id,va);
  tma[node].first=max(tma[le].first,tma[ri].first);
  tma[node].second=max(tma[le].second,tma[ri].second);
  tmi[node].first=min(tmi[le].first,tmi[ri].first);
  tmi[node].second=min(tmi[le].second,tmi[ri].second);
}
vector<int> nodes;
void query(int node,int a,int b,int l,int r){
  if(a>r or l>b) return;
  if(l<=a and r>=b){
    nodes.push_back(node);
    return;
  }
  iii res,le,ri;
  int mid=(a+b)/2;
  query(2*node+1,a,mid,l,r);
  query(2*node+2,mid+1,b,l,r);
}
void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
  ns=(H*W);
  for(int i=0;i<R.size();i++){
    val[i]=ii(R[i],C[i]);
  }
  init(0,0,ns-1);
}

int swap_seats(int a, int b) {
  int res=0;
  ii u,v;
  u=val[a];
  v=val[b];
  swap(val[a],val[b]);
  update(0,0,ns-1,a,v);
  update(0,0,ns-1,b,u);
  bool sw=0;
  int ri,ra,ca,ci;
  ri=ci=MAX;
  ca=ra=-1;
  for(int i=0;i<ns;i++){
    if(sw==0){
      ri=min(ri,val[i].first);
      ra=max(ra,val[i].first);
      ca=max(ca,val[i].second);
      ci=min(ci,val[i].second);
    }
    else{
      nodes.clear();
      query(0,0,ns-1,0,i);
      for(int j=0;j<nodes.size();j++){
	ri=min(ri,tmi[nodes[j]].first); ci=min(ci,tmi[nodes[j]].second);
	ra=max(ra,tma[nodes[j]].first); ca=max(ca,tma[nodes[j]].second);
      }
      sw=0;
    }
    if(((ra-ri)+1)*((ca-ci)+1)==i+1) res++;
    if(((ra-ri)+1)*((ca-ci)+1)>i+1){sw=1; i=((ra-ri)+1)*((ca-ci)+1)-2;}
  }
  return res;
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int i=0;i<R.size();i++){
      |               ~^~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:82:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |       for(int j=0;j<nodes.size();j++){
      |                   ~^~~~~~~~~~~~~

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