This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
bool has[maxn];
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;
if(val == -1 && !has[k])
return;
if(val == 1 && has[k])
return;
has[k] ^= 1;
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);
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:70:12: warning: division by zero [-Wdiv-by-zero]
cout << 1/0;
~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |