제출 #623350

#제출 시각아이디문제언어결과실행 시간메모리
623350AlperenTMinerals (JOI19_minerals)C++17
100 / 100
471 ms17024 KiB
#include <bits/stdc++.h> #include "minerals.h" using namespace std; const int N = 50000 + 5; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, ans[N], ptr, cnt; vector<int> a, b; set<int> cur; int query(int x){ if(cur.find(x) != cur.end()) cur.erase(x); else cur.insert(x); return cnt = Query(x); } struct SegTree{ map<int, vector<int>> tree; void build(int v = 1, int l = 1, int r = n, bool flag = false){ if(l > r) return; if(l == r) ans[l] = tree[v].front(); else{ int m = l + (r - l) * 0.373; for(int i = l; i <= m; i++) query(a[i - 1]); for(auto x : tree[v]){ if(tree[v * 2].size() == (m - l + 1)) tree[v * 2 + 1].push_back(x); else if(tree[v * 2 + 1].size() == (r - (m + 1) + 1)) tree[v * 2].push_back(x); else{ if(cur.find(x) == cur.end()){ int prevcnt = cnt; query(x); if(prevcnt + 1 == cnt) tree[v * 2 + flag].push_back(x); else tree[v * 2 + !flag].push_back(x); } else{ int prevcnt = cnt; query(x); if(prevcnt == cnt) tree[v * 2 + !flag].push_back(x); else tree[v * 2 + flag].push_back(x); } } } build(v * 2, l, m, !flag); build(v * 2 + 1, m + 1, r, flag); } } }; SegTree sgt; void Solve(int N_) { n = N_; for(int i = 1; i <= n * 2; i++){ int prvcnt = cnt; query(i); if(cnt == prvcnt + 1) a.push_back(i); else b.push_back(i); } for(auto x : b) sgt.tree[1].push_back(x); sgt.build(); for(int i = 1; i <= n; i++) Answer(a[i - 1], ans[i]); }

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

minerals.cpp: In member function 'void SegTree::build(int, int, int, bool)':
minerals.cpp:36:39: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |                 if(tree[v * 2].size() == (m - l + 1)) tree[v * 2 + 1].push_back(x);
      |                    ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
minerals.cpp:37:48: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |                 else if(tree[v * 2 + 1].size() == (r - (m + 1) + 1)) tree[v * 2].push_back(x);
      |                         ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...