Submission #75089

#TimeUsernameProblemLanguageResultExecution timeMemory
75089ics0503Seats (IOI18_seats)C++17
100 / 100
3087 ms153192 KiB
#include "seats.h" #include<vector> #include<algorithm> #include<stdlib.h> using namespace std; int h, w, n; struct ND {int am, as, bm, bs, S, alaz,blaz;}tree[4141414]; int min(int a, int b) { if (a < b)return a; return b; } int max(int a, int b) { if (a > b)return a; return b; } void update(int w) { int c1 = w << 1, c2 = (w << 1) + 1; tree[w].am = min(tree[c1].am, tree[c2].am); tree[w].bm = min(tree[c1].bm, tree[c2].bm); tree[w].as = tree[w].bs = tree[w].S = 0; if (tree[w].am == tree[c1].am)tree[w].as += tree[c1].as; if (tree[w].am == tree[c2].am)tree[w].as += tree[c2].as; if (tree[w].bm == tree[c1].bm)tree[w].bs += tree[c1].bs; if (tree[w].bm == tree[c2].bm)tree[w].bs += tree[c2].bs; if (tree[w].am == tree[c1].am && tree[w].bm == tree[c1].bm)tree[w].S += tree[c1].S; if (tree[w].am == tree[c2].am && tree[w].bm == tree[c2].bm)tree[w].S += tree[c2].S; } void lazy(int w) { if (tree[w].alaz == 0 && tree[w].blaz == 0)return; int c1 = w << 1, c2 = (w << 1) + 1; tree[c1].alaz += tree[w].alaz, tree[c2].alaz += tree[w].alaz; tree[c1].blaz += tree[w].blaz, tree[c2].blaz += tree[w].blaz; tree[c1].am += tree[w].alaz; tree[c2].am += tree[w].alaz; tree[c1].bm += tree[w].blaz; tree[c2].bm += tree[w].blaz; tree[w].alaz = tree[w].blaz = 0; } void insert_g(int w, int s, int e, int l, int r, int tp, int g) { if (s != e)lazy(w); if (s == l&&e == r) { if (tp == 0) { tree[w].alaz += g; tree[w].am += g; } else{ tree[w].blaz += g; tree[w].bm += g; } return; } int m = (s + e) >> 1; if (l <= m)insert_g(w * 2, s, m, l, min(m, r), tp, g); if (m + 1 <= r)insert_g(w * 2 + 1, m + 1, e, max(m + 1, l), r, tp, g); update(w); } int x[1212121], y[1212121]; vector<int>M[1212121]; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; int A[1212121], B[1212121]; void init(int w, int s, int e) { if (s == e) { tree[w].am = A[s], tree[w].bm = B[s], tree[w].S = tree[w].as = tree[w].bs = 1; return; } int m = (s + e) >> 1; init(w * 2, s, m); init(w * 2 + 1, m + 1, e); update(w); } int AT[1212121], BT[1212121]; vector<pair<pair<pair<int, int>, int>, int>>QQ; void go_1(int x, int y, int g, int tp = 0) { int i; for (i = 0; i < 4; i++) { int ni = (i + 1) % 4; int nx = x + dx[i], ny = y + dy[i]; int nnx = x + dx[ni], nny = y + dy[ni]; int si, ei; si = M[x][y], ei = min(M[nx][ny], M[nnx][nny]) - 1; if (si <= ei) { if (tp == 0)QQ.push_back({ {{ si, ei },0}, g }); else AT[si] += g, AT[ei + 1] -= g; } si = max(M[nx][ny], M[nnx][nny]), ei = M[x][y] - 1; if (si <= ei) { if (tp == 0)QQ.push_back({ {{ si, ei },1}, g }); else BT[si] += g, BT[ei + 1] -= g; } } } void go_2(int x, int y,int rx,int ry, int g) { int i; for (i = 0; i < 4; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx == rx&&ny == ry)continue; int ni, nnx, nny, si, ei; ni = (i + 1) % 4; nnx = nx + dx[ni], nny = ny + dy[ni]; si = M[nx][ny], ei = min(M[x][y], M[nnx][nny]) - 1; if (si <= ei)QQ.push_back({ { { si, ei },0 }, g }); si = max(M[x][y], M[nnx][nny]), ei = M[nx][ny] - 1; if (si <= ei)QQ.push_back({ { { si, ei },1 }, g }); ni = (i + 3) % 4; nnx = nx + dx[ni], nny = ny + dy[ni]; si = M[nx][ny], ei = min(M[x][y], M[nnx][nny]) - 1; if (si <= ei)QQ.push_back({ { { si, ei },0 }, g }); si = max(M[x][y], M[nnx][nny]), ei = M[nx][ny] - 1; if (si <= ei)QQ.push_back({ { { si, ei },1 }, g }); } } void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { int i, j; h = H, w = W; n = H*W; for (i = 0; i <= h + 1; i++) for (j = 0; j <= w + 1; j++)M[i].push_back(n + 1); for (i = 0; i < n; i++)x[i + 1] = R[i] + 1, y[i + 1] = C[i] + 1; for (i = 1; i <= n; i++) M[x[i]][y[i]] = i; for (i = 1; i <= h; i++) for (j = 1; j <= w; j++) go_1(i, j, 1, 1); for (i = 1; i <= n; i++)A[i] = A[i - 1] + AT[i], B[i] = B[i - 1] + BT[i]; init(1, 1, n); } void swap(int &a, int &b) { int c = a; a = b; b = c; } int swap_seats(int a, int b) { QQ.clear(); a++, b++; go_1(x[a], y[a], -1); go_2(x[a], y[a], x[b], y[b], -1); go_1(x[b], y[b], -1); go_2(x[b], y[b], x[a], y[a], -1); swap(x[a], x[b]), swap(y[a], y[b]); swap(M[x[a]][y[a]], M[x[b]][y[b]]); go_1(x[a], y[a], 1); go_2(x[a], y[a], x[b], y[b], 1); go_1(x[b], y[b], 1); go_2(x[b], y[b], x[a], y[a], 1); sort(QQ.begin(), QQ.end()); vector<pair<pair<pair<int, int>,int>, int>>RQQ; for (int i = 0; i < QQ.size(); i++) { if (RQQ.empty() || RQQ.back().first != QQ[i].first)RQQ.push_back(QQ[i]); else RQQ.back().second += QQ[i].second; } for (int i = 0; i < RQQ.size(); i++) insert_g(1, 1, n, RQQ[i].first.first.first, RQQ[i].first.first.second, RQQ[i].first.second, RQQ[i].second); return tree[1].S; }

Compilation message (stderr)

seats.cpp: In function 'int swap_seats(int, int)':
seats.cpp:125:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < QQ.size(); i++) {
                  ~~^~~~~~~~~~~
seats.cpp:129:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < RQQ.size(); i++) insert_g(1, 1, n, RQQ[i].first.first.first, RQQ[i].first.first.second, RQQ[i].first.second, RQQ[i].second);
                  ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...