Submission #295606

#	Time	Username	Problem	Language	Result	Execution time	Memory
295606		DanerZein	Seats (IOI18_seats)	C++14	0 / 100	488 ms	56716 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define MAX 1000000000
using namespace std;
typedef pair<int,int> ii;
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(tma[2*node+1].first,tmi[2*node+2].first);
  tmi[node].second=min(tma[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);
}
ii queryma(int node,int a,int b,int l,int r){
  if(a>r or l>b) return ii(-1,-1);
  if(l<=a and r>=b) return tma[node];
  ii res,le,ri;
  int mid=(a+b)/2;
  le=queryma(2*node+1,a,mid,l,r);
  ri=queryma(2*node+2,mid+1,b,l,r);
  res.first=max(le.first,ri.first);
  res.second=max(le.second,ri.second);
  return res;
}
ii querymi(int node,int a,int b,int l,int r){
  if(a>r or l>b) return ii(MAX,MAX);
  if(l<=a and r>=b) return tmi[node];
  ii res,le,ri;
  int mid=(a+b)/2;
  le=querymi(2*node+1,a,mid,l,r);
  ri=querymi(2*node+2,mid+1,b,l,r);
  res.first=min(le.first,ri.first);
  res.second=min(le.second,ri.second);
  return res;
}
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);
  /*for(int i=0;i<13;i++){
    printf("(%d,%d) ",tmi[i].first,tmi[i].second);
  }
  cout<<endl;
  for(int i=0;i<13;i++){
    printf("(%d,%d) ",tma[i].first,tma[i].second);
  }
  cout<<endl;*/
  for(int i=0;i<ns;i++){
    u=queryma(0,0,ns-1,0,i);
    v=querymi(0,0,ns-1,0,i);
    int ri,ra,ca,ci;
    ri=v.first; ci=v.second;
    ra=u.first; ca=u.second;
    //cout<<i<<" "<<ri<<" "<<ci<<" "<<ra<<" "<<ca<<'\n';
    if(((ra-ri)+1)*((ca-ci)+1)==i+1) res++;
    if(((ra-ri)+1)*((ca-ci)+1)>i+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:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i=0;i<R.size();i++){
      |               ~^~~~~~~~~

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