| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 943741 |
2024-03-11T19:28:05 Z |
Lobo |
Seats (IOI18_seats) |
C++17 |
|
1787 ms |
110708 KB |
#include "seats.h"
#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 1e6+10;
const int B = 1000;
int n, m, col[maxn], row[maxn];
vector<vector<int>> grid;
int trmn[4*maxn], trq[4*maxn], lz[4*maxn];
void build(int no, int l, int r) {
trq[no] = r-l+1;
trmn[no] = 0;
if(l == r) return;
int lc=2*no,rc=2*no+1,mid=(l+r)/2;
build(lc,l,mid);
build(rc,mid+1,r);
}
void flush(int no, int l, int r) {
trmn[no]+= lz[no];
if(l != r) {
int lc=2*no,rc=2*no+1;
lz[lc]+= lz[no];
lz[rc]+= lz[no];
}
lz[no] = 0;
}
void upd(int no, int l, int r, int ll, int rr, int val) {
flush(no,l,r);
if(l > rr or r < ll) return;
if(l >= ll && r <= rr) {
lz[no] = val;
flush(no,l,r);
return;
}
int lc=2*no,rc=2*no+1,mid=(l+r)/2;
upd(lc,l,mid,ll,rr,val);
upd(rc,mid+1,r,ll,rr,val);
trmn[no] = min(trmn[lc],trmn[rc]);
trq[no] = 0;
if(trmn[no] == trmn[lc]) trq[no]+= trq[lc];
if(trmn[no] == trmn[rc]) trq[no]+= trq[rc];
}
void construct(int i, int j, int dx) {
vector<int> times;
for(int di = 0; di <= 1; di++) {
for(int dj = 0; dj <= 1; dj++) {
if(i+di >= 0 && i+di < n && j+dj >= 0 && j+dj < m) {
times.pb(grid[i+di][j+dj]);
}
}
}
sort(all(times));
for(int i = 0; i < (int) times.size(); i++) {
int tl = times[i];
int tr;
if(i+1 < (int) times.size()) tr = times[i+1]-1;
else tr = n*m-1;
if(i+1 == 1) upd(1,0,n*m-1,tl,tr,+1*dx);
if(i+1 == 3) upd(1,0,n*m-1,tl,tr,+5*dx);
}
}
void give_initial_chart(int32_t H, int32_t W, std::vector<int32_t> R, std::vector<int32_t> C) {
n = H;
m = W;
grid.resize(n,vector<int>(m));
for(int i = 0; i < n*m; i++) {
col[i] = C[i];
row[i] = R[i];
grid[row[i]][col[i]] = i;
}
build(1,0,n*m-1);
for(int i = -1; i < n; i++) {
for(int j = -1; j < m; j++) {
construct(i,j,1);
}
}
}
int32_t swap_seats(int32_t a, int32_t b) {
int i,j;
set<pair<int,int>> st;
i = row[a];
j = col[a];
for(int di = 0; di <= 1; di++) {
for(int dj = 0; dj <= 1; dj++) {
if(i+di >= -1 && i+di < n && j+dj >= -1 && j+dj < m) {
st.insert(mp(i+di,j+dj));
}
}
}
i = row[b];
j = col[b];
for(int di = 0; di <= 1; di++) {
for(int dj = 0; dj <= 1; dj++) {
if(i+di >= -1 && i+di < n && j+dj >= -1 && j+dj < m) {
st.insert(mp(i+di,j+dj));
}
}
}
for(auto x : st) {
construct(x.fr,x.sc,-1);
}
swap(col[a],col[b]);
swap(row[a],row[b]);
grid[row[a]][col[a]] = a;
grid[row[b]][col[b]] = b;
for(auto x : st) {
construct(x.fr,x.sc,+1);
}
return trq[1];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1787 ms |
94788 KB |
Output is correct |
| 2 |
Incorrect |
927 ms |
110708 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
11100 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
9600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
