Submission #297726

#	Time	Username	Problem	Language	Result	Execution time	Memory
297726		DanerZein	Seats (IOI18_seats)	C++14	0 / 100	426 ms	92160 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];
int cma[1000010],rma[1000010];
int cmi[1000010],rmi[1000010];
int bea[1000010];
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]);
  }
  cma[0]=cmi[0]=C[0];
  rma[0]=rmi[0]=R[0];
  bea[0]=1;
  for(int i=1;i<ns;i++){
    cma[i]=max(cma[i-1],C[i]);
    cmi[i]=min(cmi[i-1],C[i]);
    rma[i]=max(rma[i-1],R[i]);
    rmi[i]=min(rmi[i-1],R[i]);
    int ar=((cma[i]-cmi[i])+1)*((rma[i]-rmi[i])+1);
    if(ar==i+1) bea[i]=bea[i-1]+1;
    else bea[i]=bea[i-1];
  }
  init(0,0,ns-1);
}

int swap_seats(int a, int b) {
  if(abs(a-b)<=10000){
    swap(val[a],val[b]);
    for(int i=min(a,b);i<=max(a,b);i++){
      if(i==0){
	cma[i]=val[i].second;
	cmi[i]=val[i].second;
	rma[i]=val[i].first;
	rmi[i]=val[i].first;
	bea[i]=1;
      }
      else{
	cma[i]=max(cma[i-1],val[i].second);
	cmi[i]=min(cmi[i-1],val[i].second);
	rma[i]=max(rma[i-1],val[i].first);
	rmi[i]=min(rmi[i-1],val[i].first);
	int ar=((cma[i]-cmi[i])+1)*((rma[i]-rmi[i])+1);
	if(ar==i+1) bea[i]=bea[i-1]+1;
	else bea[i]=bea[i-1];
      }
    }
    return bea[ns-1];
  }
  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:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int i=0;i<R.size();i++){
      |               ~^~~~~~~~~
seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |       for(int j=0;j<nodes.size();j++){
      |                   ~^~~~~~~~~~~~~

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