Submission #138562

#	Time	Username	Problem	Language	Result	Execution time	Memory
138562		Mahdi_Jfri	Seats (IOI18_seats)	C++14	0 / 100	4088 ms	32304 KiB

seats

#include "seats.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 1e6 + 20;

int n , a[maxn] , pos[maxn] , cnt[maxn * 4] , mn[maxn * 4] , Add[maxn * 4];

void build(int s = 0 , int e = n , int v = 1)
{
	cnt[v] = e - s;
	if(e - s < 2)
		return;

	int m = (s + e) / 2;
	build(s , m , 2 * v);
	build(m , e , 2 * v + 1);
}

void add(int l , int r , int val , int s = 0 , int e = n , int v = 1)
{
	if(l <= s && e <= r)
	{
		Add[v] += val;
		mn[v] += val;
		return;
	}
	if(r <= s || e <= l)
		return;

	int m = (s + e) / 2;
	add(l , r , val , s , m , 2 * v);
	add(l , r , val , m , e , 2 * v + 1);

	mn[v] = min(mn[2 * v] , mn[2 * v + 1]);
	cnt[v] = 0;

	if(mn[v] == mn[2 * v])
		cnt[v] += cnt[2 * v];
	if(mn[v] == mn[2 * v + 1])
		cnt[v] += cnt[2 * v + 1];

	mn[v] += Add[v];
}

void d(int k , int val)
{
	if(k < 0 || k > n)
		return;
	add(pos[k] , n , pos[k - 1] < pos[k]? -1 * val : 1 * val);
	add(pos[k] , n , pos[k + 1] < pos[k]? -1 * val : 1 * val);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C)
{
	n = H * W;
	if(H != 1)
		cout << 1/0;
	build();
	for(int i = 0; i < n; i++)
	{
		a[i] = C[i] + 1;
		pos[a[i]] = i;
	}
	pos[0] = pos[n + 1] = 1e9;

	for(int i = 0; i < n; i++)
		d(a[i] , 1);
}

int swap_seats(int x, int y)
{
	for(int i = -1; i <= 1; i++)
		d(a[x] + i , -1) , d(a[y] + i , -1);

	swap(a[x] , a[y]);
	swap(pos[a[x]] , pos[a[y]]);

	for(int i = -1; i <= 1; i++)
		d(a[x] + i , 1) , d(a[y] + i , 1);
  
  	while(mn[1] < 2);

	if(mn[1] != 2)
		return 0;
	else
		return cnt[1];
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:62:12: warning: division by zero [-Wdiv-by-zero]
   cout << 1/0;
           ~^~

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