제출 #295629

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295629		DanerZein	Seats (IOI18_seats)	C++14	5 / 100	4065 ms	57336 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(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);
}
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);
  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{
      u=queryma(0,0,ns-1,0,i);
      v=querymi(0,0,ns-1,0,i);
      ri=v.first; ci=v.second;
      ra=u.first; ca=u.second;
    }
    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;
}

컴파일 시 표준 에러 (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: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 0 / 33
• Subtask 6: 0 / 30