Submission #603795

#	Time	Username	Problem	Language	Result	Execution time	Memory
603795		CSQ31	Seats (IOI18_seats)	C++17	25 / 100	4097 ms	98552 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int>pii;
int n;
struct node{
	int mn = 1e9,mx = -1e9;
	node(){}
};
struct seg{
	vector<int>a;
	vector<node>t;
	int N;
	void build(int v,int l,int r){
		if(l==r){
			t[v].mn = t[v].mx = a[l];
			return;
		}
		int tm = (l+r)/2;
		build(2*v,l,tm);
		build(2*v+1,tm+1,r);
		t[v].mn = min(t[2*v].mn,t[2*v+1].mn);
		t[v].mx = max(t[2*v].mx,t[2*v+1].mx);
	}
	seg(){}
	seg(int _N,vector<int>_a){
		N = _N;
		a = _a;
		t.resize(4*N);
		build(1,0,N-1);
	}
	void upd(int v,int pos,int l,int r,int val){
		if(l==r){
			t[v].mn = t[v].mx = val;
			return;
		}
		int tm = (l+r)/2;
		if(pos<=tm)upd(2*v,pos,l,tm,val);
		else       upd(2*v+1,pos,tm+1,r,val);
		t[v].mn = min(t[2*v].mn,t[2*v+1].mn);
		t[v].mx = max(t[2*v].mx,t[2*v+1].mx);
	}
	pii query(int v,int l,int r,int tl,int tr){
		if(l>r)return {1e9,-1e9};
		if(l == tl && r == tr)return {t[v].mn,t[v].mx};
		int tm = (tl+tr)/2;
		pii a = query(2*v,l,min(r,tm),tl,tm);
		pii b = query(2*v+1,max(l,tm+1),r,tm+1,tr);
		pii c;
		c.fi = min(a.fi,b.fi);
		c.se = max(a.se,b.se);
		return c;
	}
	
	
}rr,cc;
vector<int>r,c;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
	n = H*W;
	r = R;
	c = C;
	rr = seg(n,r);
	cc = seg(n,c);
}
int swap_seats(int a, int b) {
  swap(r[a],r[b]);
  swap(c[a],c[b]);
  rr.upd(1,a,0,n-1,r[a]);
  cc.upd(1,a,0,n-1,c[a]);
  rr.upd(1,b,0,n-1,r[b]);
  cc.upd(1,b,0,n-1,c[b]);  
  int ans = 0;

  for(int i=0;i<n;){
	  pii x = rr.query(1,0,i,0,n-1);
	  pii y = cc.query(1,0,i,0,n-1);
	 // cout<<i<<" "<<x.fi<<" "<<x.se<<" "<<y.fi<<" "<<y.se<<'\n';
	  if((x.se-x.fi+1) * (y.se - y.fi+1) == i+1){
		  ans++;
		  i+=min(x.se - x.fi+1,y.se - y.fi+1);
	  }else i = (x.se-x.fi+1) * (y.se - y.fi+1) - 1;
  }
  return ans;
}

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