제출 #108673

#제출 시각아이디문제언어결과실행 시간메모리
108673RezwanArefin01자리 배치 (IOI18_seats)C++17
0 / 100
342 ms63024 KiB
#include <bits/stdc++.h> #include "seats.h" using namespace std; const int N = 1e6 + 5; vector<int> r; int n, m, a[N]; struct node { int mn, cnt, lazy; node(int mn = 0, int cnt = 1, int lazy = 0) : mn(mn), cnt(cnt), lazy(lazy) {} } t[N << 2]; void upd(int node, int x) { t[node].lazy += x; t[node].mn += x; } void shift(int node) { upd(node << 1, t[node].lazy); upd(node << 1 | 1, t[node].lazy); t[node].lazy = 0; } node merge(node L, node R) { node ret; ret.mn = min(L.mn, R.mn); ret.cnt = L.mn == R.mn ? L.cnt + R.cnt : L.mn < R.mn ? L.cnt : R.cnt; return ret ; } void build(int node, int l, int r) { if(l == r) return; int m = l + r >> 1; build(node << 1, l, m); build(node << 1 | 1, m + 1, r); t[node].cnt = r - l + 1; } void update(int node, int l, int r, int i, int j, int x) { if(r < i || l > j || i > j) return; if(i <= l && r <= j) { upd(node, x); return; } shift(node); int m = l + r >> 1; update(node << 1, l, m, i, j, x); update(node << 1 | 1, m + 1, r, i, j, x); t[node] = merge(t[node << 1], t[node << 1 | 1]); } node query(int node, int l, int r, int i, int j) { if(r < i || l > j) return {N, 0, 0}; if(i <= l && r <= j) return t[node]; shift(node); int m = l + r >> 1; return merge(query(node << 1, l, m, i, j), query(node << 1 | 1, m + 1, r, i, j)); } void change(int i, int x) { update(1, 0, n - 1, min(a[i - 1], a[i]), max(a[i - 1], a[i]) - 1, -1); update(1, 0, n - 1, min(a[i + 1], a[i]), max(a[i + 1], a[i]) - 1, -1); a[i] = x; update(1, 0, n - 1, min(a[i - 1], x), max(a[i - 1], x) - 1, +1); update(1, 0, n - 1, min(a[i + 1], x), max(a[i + 1], x) - 1, +1); } void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { n = W; for(int i = 0; i <= n + 1; ++i) a[i] = n; for(int i = 0; i < n; ++i) { change(C[i] + 1, i); } } int swap_seats(int i, int j) { ++i, ++j; int x = a[i], y = a[j]; change(i, n); change(j, n); change(i, y); change(j, x); if(t[1].mn != 2) return 0; else return t[1].cnt; }

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

seats.cpp: In function 'void build(int, int, int)':
seats.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
seats.cpp: In function 'void update(int, int, int, int, int, int)':
seats.cpp:47:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1; 
             ~~^~~
seats.cpp: In function 'node query(int, int, int, int, int)':
seats.cpp:57:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = 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...