제출 #204688

#제출 시각아이디문제언어결과실행 시간메모리
204688waynetuinfor자리 배치 (IOI18_seats)C++17
33 / 100
3458 ms99780 KiB
#include "seats.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>> gr; vector<pair<int, int>> tree; vector<int> tag; vector<pair<int, int>> pos; int n; pair<int, int> Merge(pair<int, int> a, pair<int, int> b) { if (a.first < b.first) return a; if (a.first > b.first) return b; return make_pair(a.first, a.second + b.second); } void BuildTree(int l, int r, int o = 0) { if (r - l == 1) { tree[o] = make_pair(0, 1); if (l == n - 1) tree[o].first = n * 10; return; } int m = (l + r) >> 1; BuildTree(l, m, o * 2 + 1); BuildTree(m, r, o * 2 + 2); tree[o] = Merge(tree[o * 2 + 1], tree[o * 2 + 2]); } void Push(int o) { for (int v = 1; v <= 2; ++v) { tree[o * 2 + v].first += tag[o]; tag[o * 2 + v] += tag[o]; } tag[o] = 0; } void Modify(int l, int r, int ql, int qr, int v, int o = 0) { if (l >= qr || ql >= r) return; if (l >= ql && r <= qr) { tree[o].first += v; tag[o] += v; return; } Push(o); int m = (l + r) >> 1; Modify(l, m, ql, qr, v, o * 2 + 1); Modify(m, r, ql, qr, v, o * 2 + 2); tree[o] = Merge(tree[o * 2 + 1], tree[o * 2 + 2]); } void UpdateRect(int x, int y, int v) { if (x >= gr.size() || y >= gr[0].size()) return; vector<int> w; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) w.push_back(gr[x - i][y - j]); } sort(w.begin(), w.end()); int a = w[0], b = w[1]; Modify(0, n, a, b, v); } void give_initial_chart(int h, int w, vector<int> r, vector<int> c) { gr.resize(h + 2, vector<int>(w + 2, h * w)); pos.resize(h * w); for (int i = 0; i < h * w; ++i) { gr[r[i] + 1][c[i] + 1] = i; pos[i] = make_pair(r[i] + 1, c[i] + 1); } n = h * w + 1; tree.resize(n * 4); tag.resize(n * 4); BuildTree(0, n); for (int i = 1; i <= h + 1; ++i) { for (int j = 1; j <= w + 1; ++j) UpdateRect(i, j, 1); } } int swap_seats(int a, int b) { for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) UpdateRect(pos[a].first + i, pos[a].second + j, -1); } for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) UpdateRect(pos[b].first + i, pos[b].second + j, -1); } swap(gr[pos[a].first][pos[a].second], gr[pos[b].first][pos[b].second]); swap(pos[a], pos[b]); for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) UpdateRect(pos[a].first + i, pos[a].second + j, 1); } for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) UpdateRect(pos[b].first + i, pos[b].second + j, 1); } return tree[0].second; }

컴파일 시 표준 에러 (stderr) 메시지

seats.cpp: In function 'void UpdateRect(int, int, int)':
seats.cpp:53:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (x >= gr.size() || y >= gr[0].size()) return;
         ~~^~~~~~~~~~~~
seats.cpp:53:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (x >= gr.size() || y >= gr[0].size()) return;
                           ~~^~~~~~~~~~~~~~~
#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...