제출 #115775

#제출 시각아이디문제언어결과실행 시간메모리
115775WhipppedCream자리 배치 (IOI18_seats)C++17
0 / 100
379 ms136984 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC target ("sse4") #include "seats.h" using namespace std; #define X first #define Y second #define pb push_back typedef pair<int, int> ii; typedef long long ll; const int maxn = 1e6+5; int n, m; int r[maxn]; struct node { int val, cnt, lz; node(int a = 0, int b = 0) : val(a), cnt(b) { lz = 0; } }; node st[4*maxn]; node pull(node &x, node &y) { if(x.val< y.val) return x; if(x.val> y.val) return y; return node(x.val, x.cnt+y.cnt); } void pushdown(int p, int L, int R) { if(st[p].lz == 0) return; st[p].val += st[p].lz; if(L != R) { st[2*p].lz += st[p].lz; st[2*p+1].lz += st[p].lz; } st[p].lz = 0; } void build(int p = 1, int L = 0, int R = n-1) { if(L == R) { st[p] = node(0, 1); return; } int M = (L+R)/2; build(2*p, L, M); build(2*p+1, M+1, R); st[p] = pull(st[2*p], st[2*p+1]); } void update(int i, int j, int dx, int p = 1, int L = 0, int R = n-1) { pushdown(p, L, R); if(i> R || j< L) return; if(i<= L && R<= j) { st[p].lz += dx; pushdown(p, L, R); return; } int M = (L+R)/2; update(i, j, dx, 2*p, L, M); update(i, j, dx, 2*p+1, M+1, R); st[p] = pull(st[2*p], st[2*p+1]); } node ask(int i, int j, int p = 1, int L = 0, int R = n-1) { if(i> R || j< L) return node(1e9, 0); if(i<= L && R<= j) return st[p]; int M = (L+R)/2; node x = ask(i, j, 2*p, L, M); node y = ask(i, j, 2*p+1, M+1, R); return pull(x, y); } int tim[maxn]; int tog[maxn]; void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { m = H; n = W; assert(m == 1); for(int i = 0; i< n; i++) { tim[i] = C[i]; tog[C[i]] = i; } int prv = 0; build(); for(int i = 0; i< n; i++) { int dat = tim[i]; int y = 0; if(dat && tim[tog[dat-1]]< i) y++; if(dat+1< n && tim[tog[dat+1]]< i) y++; int cur = prv + 2 - 2*y; update(i, i, cur); prv = cur; } node kk = ask(0, n-1); // printf("%d %d\n", kk.val, kk.cnt); } void add(int val, int a, int b) { int m1 = val?tog[val-1]:1e9; int m2 = val+1< n?tog[val+1]:1e9; // printf("%d %d\n", m1, m2); if(m1> m2) swap(m1, m2); update(a, min(m1-1, b), 2); // printf("[%d %d] +2\n", a, min(m1-1, b)); update(max(a, m2), b, -2); // printf("[%d %d] -2\n", max(a, m2), b); } void rem(int val, int a, int b) { int m1 = val?tog[val-1]:1e9; int m2 = val+1< n?tog[val+1]:1e9; // printf("%d %d\n", m1, m2); if(m1> m2) swap(m1, m2); update(a, min(m1-1, b), -2); // printf("[%d %d] -2\n", a, min(m1-1, b)); update(max(a, m2), b, 2); // printf("[%d %d] +2\n", max(a, m2), b); } int swap_seats(int a, int b) { if(a> b) swap(a, b); rem(tim[a], a, b-1); swap(tog[tim[a]], tog[tim[b]]); add(tim[b], a, b-1); swap(tim[a], tim[b]); node kk = ask(0, n-1); if(kk.val == 2) return kk.cnt; return 0; }

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

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:112:7: warning: variable 'kk' set but not used [-Wunused-but-set-variable]
  node kk = ask(0, n-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...