제출 #964412

#제출 시각아이디문제언어결과실행 시간메모리
964412BestCrazyNoob자리 배치 (IOI18_seats)C++17
11 / 100
4029 ms39504 KiB
#include "seats.h" #include <cassert> #include <tuple> using namespace std; struct Node { int mn, mx; Node(): mn(1e9), mx(0) {} Node(int a): mn(a), mx(a) {} Node(Node l, Node r) { mn = min(l.mn, r.mn); mx = max(l.mx, r.mx); } }; struct SegTree { int sz; vector<Node> tree; int ql, qr; SegTree() {} SegTree(vector<int> v) { sz = 1; while (sz < v.size()) sz *= 2; tree.resize(2*sz, Node()); for (int i = 0; i < v.size(); i++) tree[sz+i] = Node(v[i]); for (int i = v.size(); i < sz; i++) tree[sz+i] = Node(); for (int i = sz-1; i >= 1; i--) tree[i] = Node(tree[2*i], tree[2*i+1]); } void update(int i, int x) { i += sz; tree[i] = Node(x); while (i > 1) { i /= 2; tree[i] = Node(tree[2*i], tree[2*i+1]); } } Node __query(int ni, int nl, int nr) { if (qr <= nl || nr <= ql) return Node(); if (ql <= nl && nr <= qr) return tree[ni]; int nm = (nl+nr)/2; return Node(__query(2*ni, nl, nm), __query(2*ni+1, nm, nr)); } pair<int, int> query(int l, int r) { ql = l; qr = r; auto res = __query(1, 0, sz); return {res.mn, res.mx}; } }; // sol1 vector<int> mxC, mnC, mxR, mnR; int ans; // sol2 vector<int> R, C; SegTree rSeg, cSeg; void give_initial_chart(int H, int W, vector<int> R, vector<int> C) { assert(H <= 10'000); assert(W <= 10'000); ::R = R; ::C = C; if (C.size() > 1'000 || R.size() > 1'000) { // sol1 mxC.resize(C.size()); mnC.resize(C.size()); mxR.resize(C.size()); mnR.resize(C.size()); mxC[0] = mnC[0] = C[0]; mxR[0] = mnR[0] = R[0]; for (int i = 1; i < C.size(); i++) { mxC[i] = max(C[i], mxC[i-1]); mxR[i] = max(R[i], mxR[i-1]); mnC[i] = min(C[i], mnC[i-1]); mnR[i] = min(R[i], mnR[i-1]); } for (int i = 0; i < C.size(); i++) { ans += (mxC[i] - mnC[i] + 1) * (mxR[i] - mnR[i] + 1) == i+1; } } else { // sol2 rSeg = SegTree(R); cSeg = SegTree(C); } } int sol1(int a, int b) { // a < b WLOG if (a > b) swap(a, b); for (int i = a; i <= b; i++) { ans -= (mxC[i] - mnC[i] + 1) * (mxR[i] - mnR[i] + 1) == i+1; } swap(R[a], R[b]); swap(C[a], C[b]); if (a == 0) { mxC[0] = mnC[0] = C[0]; mxR[0] = mnR[0] = R[0]; } for (int i = max(1, a); i <= b; i++) { mxC[i] = max(C[i], mxC[i-1]); mxR[i] = max(R[i], mxR[i-1]); mnC[i] = min(C[i], mnC[i-1]); mnR[i] = min(R[i], mnR[i-1]); } for (int i = a; i <= b; i++) { ans += (mxC[i] - mnC[i] + 1) * (mxR[i] - mnR[i] + 1) == i+1; } return ans; } int sol2(int a, int b) { // update swap(R[a], R[b]); swap(C[a], C[b]); rSeg.update(a, R[a]); rSeg.update(b, R[b]); cSeg.update(a, C[a]); cSeg.update(b, C[b]); // query int i = 1, ans = 1; int mnR = R[0], mnC = C[0], mxR = R[0], mxC = C[0]; while (i < C.size()) { tie(mnR, mxR) = rSeg.query(0, i); tie(mnC, mxC) = cSeg.query(0, i); if ((mxR - mnR + 1) * (mxC - mnC + 1) == i) { ans++; i += min(mxR - mnR + 1, mxC - mnC + 1); } else { i = (mxR - mnR + 1) * (mxC - mnC + 1); } } return ans; } int swap_seats(int a, int b) { if (C.size() > 1'000 || R.size() > 1'000) return sol1(a, b); return sol2(a, b); }

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

seats.cpp: In constructor 'SegTree::SegTree(std::vector<int>)':
seats.cpp:24:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         while (sz < v.size()) sz *= 2;
      |                ~~~^~~~~~~~~~
seats.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for (int i = 0; i < v.size(); i++) tree[sz+i] = Node(v[i]);
      |                         ~~^~~~~~~~~~
seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:73:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for (int i = 1; i < C.size(); i++) {
      |                         ~~^~~~~~~~~~
seats.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for (int i = 0; i < C.size(); i++) {
      |                         ~~^~~~~~~~~~
seats.cpp: In function 'int sol2(int, int)':
seats.cpp:127:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     while (i < C.size()) {
      |            ~~^~~~~~~~~~
#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...