| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 79507 |
2018-10-14T17:06:20 Z |
Milki |
Seats (IOI18_seats) |
C++14 |
|
1488 ms |
93704 KB |
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((long long) x.size())
#define pb(x) push_back(x)
typedef long long ll;
typedef pair<int, int> point;
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
const int off = 1 << 21;
const int MAXN = 1e6 + 5;
const int INF = 1e9;
struct Tournament{
point t[2 * off];
int p[2 * off];
Tournament(){
REP(i, 2 * off)
t[i] = point(INF, 0);
}
void build(){
for(int i = off - 1; i > 0; --i)
t[i] = merge(t[i * 2], t[i * 2 + 1]);
}
void add(int x, int val){
t[x + off] = point(val, 1);
}
void prop(int x){
t[x].first += p[x];
if(x < off){
p[x * 2] += p[x];
p[x * 2 + 1] += p[x];
}
p[x] = 0;
}
point merge(point a, point b){
point ret = point(min(a.first, b.first), 0);
if(a.first == ret.first) ret.second += a.second;
if(b.first == ret.first) ret.second += b.second;
return ret;
}
void update(int x, int lo, int hi, int a, int b, int val){
if(a >= b) return;
if(lo >= a && hi <= b){
p[x] += val;
prop(x);
return;
}
prop(x);
if(lo >= b || hi <= a) return;
int mid = (lo + hi) >> 1;
update(x * 2, lo, mid, a, b, val);
update(x * 2 + 1, mid, hi, a, b, val);
t[x] = merge(t[x * 2], t[x * 2 + 1]);
}
point get(int x, int lo, int hi, int a, int b){
prop(x);
if(lo >= a && hi <= b) return t[x];
if(lo >= b || hi <= a) return point(-1, -1);
int mid = (lo + hi) >> 1;
point A = get(x * 2, lo, mid, a, b);
point B = get(x * 2 + 1, mid, hi, a, b);
return merge(A, B);
}
} T;
const int dx[4][3] = { {0, -1, -1}, {-1, -1, 0}, {0, 1, 1}, {1, 1, 0} };
const int dy[4][3] = { {-1, -1, 0}, {0, 1, 1}, {1, 1, 0}, {0, -1, -1} };
vector <int> v[MAXN];
int prefix_update(int x, int y){
int old_val = 0, val = 0;
REP(i, 4){
int cnt = 0;
REP(j, 3){
int nx = x + dx[i][j];
int ny = y + dy[i][j];
if(v[nx][ny] < v[x][y]) cnt ++;
}
if(cnt == 1) old_val ++;
}
REP(i, 4){
int cnt = 0;
REP(j, 3){
int nx = x + dx[i][j];
int ny = y + dy[i][j];
if(v[nx][ny] < v[x][y]) cnt ++;
}
if(cnt == 0) val ++;
}
return val - old_val;
}
vector <int> row, col;
int kraj;
void give_initial_chart(int H, int W, vector<int> R, vector<int> C){
REP(i, H + 2){
v[i].reserve(W + 2);
}
REP(i, H + 2)
v[i][0] = v[i][W + 1] = INF;
REP(i, W + 2)
v[0][i] = v[H + 1][i] = INF;
REP(i, H + 2)
REP(j, W + 2)
v[i][j] = INF;
row.reserve(H * W + 1); col.reserve(H * W + 1);
int pref = 0;
REP(i, H * W){
R[i] ++; C[i] ++;
row.pb(R[i]); col.pb(C[i]);
v[R[i]][C[i]] = i;
pref += prefix_update(R[i], C[i]);
T.add(i, pref);
}
T.build();
kraj = H * W;
}
void update(int x, int y, int val){
REP(i, 4){
vector <int> tmp;
REP(j, 3){
int nx = x + dx[i][j];
int ny = y + dy[i][j];
tmp.pb(v[nx][ny]);
}
tmp.pb(v[x][y]);
sort(tmp.begin(), tmp.end());
REP(j, 4)
if(tmp[j] == INF)
tmp[j] = kraj;
assert(tmp[0] != INF);
if(tmp[0] == v[x][y]){
T.update(1, 0, off, tmp[0], tmp[1], val);
T.update(1, 0, off, tmp[1], tmp[2], -val);
}
else if(tmp[1] == v[x][y]){
T.update(1, 0, off, tmp[1], tmp[2], -val);
}
/*else if(tmp[1] == v[x][y] && tmp[2] != INF)
T.update(1, 0, off, tmp[1], tmp[2], -val);
else if(tmp[1] == v[x][y] && tmp[2] == INF)
T.update(1, 0, off, tmp[1], kraj, -val);
*/
}
}
int swap_seats(int a, int b){
int x1, y1, x2, y2;
x1 = row[a], y1 = col[a];
x2 = row[b], y2 = col[b];
update(x1, y1, -1);
update(x2, y2, -1);
swap(v[x1][y1], v[x2][y2]);
swap(row[a], row[b]);
swap(col[a], col[b]);
update(x1, y1, 1);
update(x2, y2, 1);
return T.get(1, 0, off, 0, off).second;
}
/*int main() {
int H = read_int();
int W = read_int();
int Q = read_int();
std::vector<int> R(H * W), C(H * W);
for (int i = 0; i < H * W; ++i) {
R[i] = read_int();
C[i] = read_int();
}
std::vector<int> A(Q), B(Q);
for (int j = 0; j < Q; ++j) {
A[j] = read_int();
B[j] = read_int();
}
give_initial_chart(H, W, R, C);
for (int j = 0; j < Q; ++j) {
int answer = swap_seats(A[j], B[j]);
printf("%d\n", answer);
}
return 0;
} */
Compilation message
seats.cpp:15:5: warning: 'int {anonymous}::read_int()' defined but not used [-Wunused-function]
int read_int() {
^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
56824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
56824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
610 ms |
84332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
84332 KB |
Output is correct |
| 2 |
Correct |
164 ms |
84332 KB |
Output is correct |
| 3 |
Incorrect |
519 ms |
84560 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
815 ms |
84560 KB |
Output is correct |
| 2 |
Correct |
919 ms |
84560 KB |
Output is correct |
| 3 |
Correct |
909 ms |
84560 KB |
Output is correct |
| 4 |
Correct |
867 ms |
84560 KB |
Output is correct |
| 5 |
Correct |
822 ms |
84560 KB |
Output is correct |
| 6 |
Correct |
1380 ms |
93516 KB |
Output is correct |
| 7 |
Correct |
1417 ms |
93516 KB |
Output is correct |
| 8 |
Correct |
1321 ms |
93516 KB |
Output is correct |
| 9 |
Correct |
1488 ms |
93532 KB |
Output is correct |
| 10 |
Correct |
1311 ms |
93680 KB |
Output is correct |
| 11 |
Correct |
1279 ms |
93704 KB |
Output is correct |
| 12 |
Correct |
1266 ms |
93704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
56824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
