Submission #131602

#	Time	Username	Problem	Language	Result	Execution time	Memory
131602		rondojim	Seats (IOI18_seats)	C++17	Compilation error	0 ms	0 KiB

seats

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6 + 7;
 
struct segtree{
	struct node{
		int cnt, mn, lz;
 
		node(){
			mn = 0;
			cnt = 1;
			lz = 0;
		}
 
		node operator+(const node &p)const{
			node ret;
 
            ret.mn = min(mn, p.mn);
            ret.cnt = 0;
 
            if (ret.mn == mn){
            	ret.cnt += cnt;
            }
            if (ret.mn == p.mn){
            	ret.cnt += p.cnt;
            }
 
            ret.lz = 0;
 
            return ret;
		}
	}seg[4 * N];
 
	void update_lazy(int idx){
		seg[2 * idx].mn += seg[idx].lz;
		seg[2 * idx].lz += seg[idx].lz;
 
		seg[2 * idx + 1].mn += seg[idx].lz;
		seg[2 * idx + 1].lz += seg[idx].lz;
 
		seg[idx].lz = 0;
	}
 
	void update(int idx, int l, int r, int sl, int sr, int val){
		//cout << "update" << idx << " " << l << " " << r << " " << sl << " " << sr << " " << val << endl;
 
		if(l > sr || r < sl){
			return;
		}
		if(sl <= l && r <= sr){
			seg[idx].mn += val;
			seg[idx].lz += val;
 
			return;
		}
 
		update_lazy(idx);
 
		int mid = (l + r) >> 1;
 
		update(2 * idx, l, mid, sl, sr, val);
		update(2 * idx + 1, mid + 1, r, sl, sr, val);
 
		seg[idx] = seg[2 * idx] + seg[2 * idx + 1];
	}
 
	int get(){
		if(seg[1].mn == 2){
			return seg[1].cnt;
		}
 
		return 0;
	}
}st;
 
pair<int, int> p[N], mx[N], mn[N];
int ptr[N];
int h, w;
 
int ans = 0;
 
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
	h = H;
	w = W;
 
	for(int i = 0; i < (int)R.size(); i++){
		p[i].first = R[i];
		p[i].second = C[i];
	}
 
	if(h == 1){
		for(int i = 0; i < w; i++){
			ptr[p[i].second] = i;
		}
 
		for(int i = 0; i < w; i++){
			//cout << i << " i" << endl;
 
			if(p[i].second == H * W - 1){
				st.update(1, 0, w - 1, i, w - 1, 1);
 
				continue;
			}
			if(p[i].second == 0){
				st.update(1, 0, w - 1, i, w - 1, 1);
			}
 
			//cout << p[i].second + 1 << " p[i].second" << endl;
			
			int j = ptr[p[i].second + 1];
 
			//cout << j<< " j" << endl;
 
			st.update(1, 0, w - 1, min(i, j), max(i, j) - 1, 1);
		}
 
		return;
	}
 
	mx[0].first = p[0].first;
	mx[0].second = p[0].second;
	mn[0].first = p[0].first;
	mn[0].second = p[0].second;
 
	ans++;
 
	for(int i = 1; i < H * W; i++){
		mx[i].first = max(mx[i - 1].first, p[i].first);
		mx[i].second = max(mx[i - 1].second, p[i].second);
 
		mn[i].first = min(mn[i - 1].first, p[i].first);
		mn[i].second = min(mn[i - 1].second, p[i].second);
 
		if((mx[i].first - mn[i].first + 1) * (mx[i].second - mn[i].second + 1) == i + 1){
			ans++;
		}
	}
}
 
int swap_seats(int a, int b){
	if(h == 1){
		if(w == 1){
			return 1;
		}
 
		if(a == b){
			return st.get();
		}
		if(a > b){
			swap(a, b);
		}
 
		//cout << p[a].second << " p " << p[b].second << endl;
 
		if(p[a].second + 1 != p[b].second){
			int x, y;
 
			if(p[a].second != w - 1){
				x = ptr[p[a].second + 1];
 
				//cout << x << " x" << endl;
 
				st.update(1, 0, w - 1, min(a, x), max(a, x) - 1, -1);
				st.update(1, 0, w - 1, min(b, x), max(b, x) - 1, 1);
			}
			else{
				st.update(1, 0, w - 1, a, w - 1, -1);
				st.update(1, 0, w - 1, b, w - 1, 1);
			}
 
			if(p[b].second != 0){
				y = ptr[p[b].second - 1];
 
				//cout << y << " y" << endl; 
 
				st.update(1, 0, w - 1, min(b, y), max(b, y) - 1, -1);
				st.update(1, 0, w - 1, min(a, y), max(a, y) - 1, 1);
			}
			else{
				st.update(1, 0, w - 1, a, w - 1, 1);
				st.update(1, 0, w - 1, b, w - 1, -1);
			}
		}
		if(p[a].second != p[b].second + 1){
			int x, y;
 
			if(p[a].second != 0){
				x = ptr[p[a].second - 1];
 
				//cout << x << " x" << endl;
 
				st.update(1, 0, w - 1, min(a, x), max(a, x) - 1, -1);
				st.update(1, 0, w - 1, min(b, x), max(b, x) - 1, 1);
			}
			else{
				st.update(1, 0, w - 1, a, w - 1, -1);
				st.update(1, 0, w - 1, b, w - 1, 1);
			}
 
			if(p[b].second != w - 1){
				y = ptr[p[b].second + 1];
 
				//cout << y << " y" << endl;
 
				st.update(1, 0, w - 1, min(b, y), max(b, y) - 1, -1);
				st.update(1, 0, w - 1, min(a, y), max(a, y) - 1, 1);
			}
			else{
				st.update(1, 0, w - 1, a, w - 1, 1);
				st.update(1, 0, w - 1, b, w - 1, -1);
			}
		}
 
		swap(p[a], p[b]);
		swap(ptr[p[a].second], ptr[p[b].second]);
 
		return st.get();
	}
 
	swap(p[a], p[b]);
 
	if(a > b){
		swap(a, b);
	}
 
	for(int i = a; i <= b; i++){
		if((mx[i].first - mn[i].first + 1) * (mx[i].second - mn[i].second + 1) == i + 1){
			ans--;
		}
 
		if(i){
			mx[i].first = max(mx[i - 1].first, p[i].first);
			mx[i].second = max(mx[i - 1].second, p[i].second);
 
			mn[i].first = min(mn[i - 1].first, p[i].first);
			mn[i].second = min(mn[i - 1].second, p[i].second);
		}
		else{
			mx[0].first = p[0].first;
			mx[0].second = p[0].second;
			mn[0].first = p[0].first;
			mn[0].second = p[0].second;
		}
 
		if((mx[i].first - mn[i].first + 1) * (mx[i].second - mn[i].second + 1) == i + 1){
			ans++;
		}
	}
 
	return ans;
}
 
/*int main(){
	int H, W;
 
	cin >> H >> W;
 
	vector<int> R, C; 
 
	for(int i = 0; i < H * W; i++){
		int x;
 
		cin >> x;
 
		R.push_back(x);
	}
 
	for(int i = 0; i < H * W; i++){
		int x;
 
		cin >> x;
 
		C.push_back(x);
	}
 
	give_initial_chart(H, W, R, C);
 
	while(true){
		int a, b;
 
		cin >> a >> b;
 
		//cout << swap_seats(a, b) << endl;
	}

Compilation message (stderr)

seats.cpp:255:1: error: unterminated comment
 /*int main(){
 ^