제출 #540171

#제출 시각아이디문제언어결과실행 시간메모리
540171cig32운세 보기 2 (JOI14_fortune_telling2)C++17
100 / 100
220 ms42884 KiB
#include "bits/stdc++.h" using namespace std; const int MAXN = 2e5 + 10; const int MOD = 1e9 + 7; #define int long long #define ll __int128 mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count()); int rnd(int x, int y) { int u = uniform_int_distribution<int>(x, y)(rng); return u; } ll read() { // read int128 int x; cin >> x; return (ll)x; } long long bm(long long b, long long p) { if(p==0) return 1 % MOD; long long r = bm(b, p >> 1); if(p&1) return (((r*r) % MOD) * b) % MOD; return (r*r) % MOD; } long long inv(long long b) { return bm(b, MOD-2); } long long f[MAXN]; long long nCr(int n, int r) { long long ans = f[n]; ans *= inv(f[r]); ans %= MOD; ans *= inv(f[n-r]); ans %= MOD; return ans; } void precomp() { for(int i=0; i<MAXN; i++) f[i] = (i == 0 ? 1 % MOD : (f[i-1] * i) % MOD); } struct query { int a, b; int mi, ma; }; bool cmp(query x, query y) { return x.ma < y.ma; } struct segtree { struct node { int mi, cntmi; int ma, cntma; }; vector<node> st; int stok; void bu(int l, int r, int idx) { if(l == r) { st[idx].mi = 0; st[idx].ma = 0; st[idx].cntmi = 1; st[idx].cntma = 1; return; } int mid = (l + r) >> 1; bu(l, mid, 2*idx+1); bu(mid+1, r, 2*idx+2); st[idx].mi = 0, st[idx].ma = 0; st[idx].cntmi = st[2*idx+1].cntmi + st[2*idx+2].cntmi; st[idx].cntma = st[2*idx+1].cntma + st[2*idx+2].cntma; } void u(int l, int r, int tar, int idx, int val) { if(l == r) { st[idx].mi = st[idx].ma = val; return; } int mid = (l+r) >> 1; if(tar <= mid) u(l, mid, tar, 2*idx+1, val); else u(mid+1, r, tar, 2*idx+2, val); st[idx].mi = min(st[2*idx+1].mi, st[2*idx+2].mi); st[idx].ma = max(st[2*idx+1].ma, st[2*idx+2].ma); if(st[2*idx+1].mi == st[2*idx+2].mi) st[idx].cntmi = st[2*idx+1].cntmi + st[2*idx+2].cntmi; else st[idx].cntmi = (st[2*idx+1].mi < st[2*idx+2].mi ? st[2*idx+1].cntmi : st[2*idx+2].cntmi); if(st[2*idx+1].ma == st[2*idx+2].ma) st[idx].cntma = st[2*idx+1].cntma + st[2*idx+2].cntma; else st[idx].cntma = (st[2*idx+1].ma > st[2*idx+2].ma ? st[2*idx+1].cntma : st[2*idx+2].cntma); } int qu1(int l, int r, int constl, int constr, int idx, int val) { if(l <= constl && constr <= r) { if(st[idx].ma < val) return -1; while(constl < constr) { int mid = (constl +constr) >> 1; if(st[2*idx+2].ma >= val) constl = mid + 1, idx = 2*idx + 2; else constr = mid, idx = 2*idx + 1; } return constl; } int mid = (constl + constr) >> 1; if(mid < l || r <constl) return qu1(l, r, mid+1, constr, 2*idx+2, val); else if(constr < l || r < mid+1) return qu1(l, r, constl, mid, 2*idx+1, val); else { int res = qu1(l, r, mid+1, constr, 2*idx+2, val); if(res != -1) return res; return qu1(l, r, constl, mid, 2*idx+1, val); } } pair<int, int> qu2(int l, int r, int constl, int constr, int idx) { if(l<=constl && constr<=r) return {st[idx].mi, st[idx].cntmi}; int mid = (constl +constr) >> 1; if(mid < l || r < constl) return qu2(l, r, mid+1, constr, 2*idx+2); else if(constr < l || r <mid+1) return qu2(l,r ,constl, mid, 2*idx+1); else { pair<int, int> lchild = qu2(l, r, constl, mid, 2*idx+1); pair<int, int> rchild = qu2(l, r, mid+1, constr, 2*idx+2); if(lchild.first != rchild.first) return min(lchild, rchild); else return {lchild.first, lchild.second + rchild.second}; } } public: void resize(int k) { stok = k; st.resize(4*k + 10); } void build() { bu(1, stok, 0); } void point_update(int i, int v) { u(1, stok, i, 0, v); } int last_atleast(int l, int r, int v) { return qu1(l, r, 1, stok, 0, v); } pair<int, int> min_cnt(int l, int r) { return qu2(l, r, 1, stok, 0); } }; void solve(int tc) { segtree st; int n, k; cin >> n >> k; st.resize(k); st.build(); query q[n]; for(int i=0; i<n; i++) { cin >> q[i].a >> q[i].b; q[i].mi = min(q[i].a, q[i].b); q[i].ma = max(q[i].a, q[i].b); } sort(q, q+n, cmp); vector<pair<int, int> > v; for(int i=1; i<=k; i++) { int y; cin >> y; v.push_back({y, i}); } sort(v.begin(), v.end()); int vptr = 0; int res = 0; for(int i=0; i<n; i++) { int og = res; while(vptr != v.size() && v[vptr].first < q[i].ma) { st.point_update(v[vptr].second, v[vptr].first); //cout << "st[" << v[vptr].second << "] := " << v[vptr].first << "\n"; vptr++; } //cout << "original: " << q[i].a << ", final: "; int idx = st.last_atleast(1, k, q[i].mi); if(idx == -1) { // A operations only pair<int, int> ono = st.min_cnt(1, k); if(ono.first == 0 && ono.second % 2 == 1) { // changed res += q[i].b; } else { res += q[i].a; } } else if(q[i].a == q[i].b) { // doesn't matter res += q[i].a; } else if(idx + 1 > k) { // last operation is S res += q[i].ma; } else { //cout << "!!! " << idx << " "; pair<int, int> ono = st.min_cnt(idx + 1, k); //cout << ono.second << " "; if(ono.first == 0 && ono.second % 2 == 1) { // changed res += q[i].mi; } else { res += q[i].ma; } } //cout << res - og << '\n'; } cout << res << '\n'; } int32_t main(){ precomp(); ios::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; for(int i=1; i<=t; i++) solve(i); } /* 6 6 1 13 14 23 5 17 10 23 6 10 12 18 10 20 19 17 21 30 */

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

fortune_telling2.cpp: In function 'void solve(long long int)':
fortune_telling2.cpp:156:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     while(vptr != v.size() && v[vptr].first < q[i].ma) {
      |           ~~~~~^~~~~~~~~~~
fortune_telling2.cpp:155:9: warning: unused variable 'og' [-Wunused-variable]
  155 |     int og = res;
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...