제출 #1010935

#제출 시각아이디문제언어결과실행 시간메모리
1010935boris_mihov자리 배치 (IOI18_seats)C++17
0 / 100
211 ms110556 KiB
#include "seats.h" #include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> typedef long long llong; const int MAXN = 1000000 + 10; const int INF = 1e9; int n, m; struct SegmentTreeLazy { struct Node { int min; int cnt; int lazy; Node() { min = cnt = lazy = 0; } friend Node operator + (const Node &left, const Node &right) { Node res; res.min = std::min(left.min, right.min); if (res.min == left.min) res.cnt += left.cnt; if (res.min == right.min) res.cnt += right.cnt; return res; } }; Node tree[4*MAXN]; void build(int l, int r, int node) { if (l == r) { tree[node].min = 0; tree[node].cnt = 1; return; } int mid = l + r >> 1; build(l, mid, 2*node); build(mid + 1, r, 2*node + 1); tree[node] = tree[2*node] + tree[2*node + 1]; } void push(int node, int l, int r) { if (tree[node].lazy == 0) { return; } tree[node].min += tree[node].lazy; if (l < r) { tree[2*node].lazy += tree[node].lazy; tree[2*node + 1].lazy += tree[node].lazy; } tree[node].lazy = 0; } void update(int l, int r, int node, int queryL, int queryR, int queryVal) { push(node, l, r); if (queryR < l || r < queryL) { return; } if (queryL <= l && r <= queryR) { tree[node].lazy = queryVal; push(node, l, r); return; } int mid = l + r >> 1; update(l, mid, 2*node, queryL, queryR, queryVal); update(mid + 1, r, 2*node + 1, queryL, queryR, queryVal); tree[node] = tree[2*node] + tree[2*node + 1]; } Node query(int l, int r, int node, int queryL, int queryR) { push(node, l, r); if (queryL <= l && r <= queryR) { return tree[node]; } Node res; res.min = INF; int mid = l + r >> 1; if (queryL <= mid) res = res + query(l, mid, 2*node, queryL, queryR); if (mid + 1 <= queryR) res = res + query(mid + 1, r, 2*node + 1, queryL, queryR); return res; } void build() { build(1, n * m, 1); } void update(int l, int r, int val) { update(1, n * m, 1, l, r, val); } int query(int l, int r) { Node res = query(1, n * m, 1, l, r); return res.cnt; } }; SegmentTreeLazy tree; std::vector <int> t[MAXN]; std::vector <int> row, col; void add(int idx) { tree.update(std::min(t[1][idx], t[1][idx - 1]), std::max(t[1][idx], t[1][idx - 1]) - 1, 1); } void rem(int idx) { tree.update(std::min(t[1][idx], t[1][idx - 1]), std::max(t[1][idx], t[1][idx - 1]) - 1, -1); } void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) { n = H; m = W; for (int i = 1 ; i <= n + 1 ; ++i) { t[i].resize(m + 2, n * m + 1); } for (int &val : R) val++; for (int &val : C) val++; row = R; col = C; for (int i = 1 ; i <= n * m ; ++i) { t[R[i - 1]][C[i - 1]] = i; } tree.build(); for (int i = 1 ; i <= m + 1 ; ++i) { add(i); } } int swap_seats(int a, int b) { a++; b++; int posA = col[a]; int posB = col[b]; rem(posA); rem(posB); rem(posA + 1); rem(posB + 1); std::swap(t[1][posA], t[1][posB]); std::swap(col[a], col[b]); add(posA); add(posB); add(posA + 1); add(posB + 1); return tree.query(1, n * m); }

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

seats.cpp: In member function 'void SegmentTreeLazy::build(int, int, int)':
seats.cpp:46:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'void SegmentTreeLazy::update(int, int, int, int, int, int)':
seats.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int mid = l + r >> 1;
      |                   ~~^~~
seats.cpp: In member function 'SegmentTreeLazy::Node SegmentTreeLazy::query(int, int, int, int, int)':
seats.cpp:99:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |         int mid = l + r >> 1;
      |                   ~~^~~
#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...