Submission #569188

#TimeUsernameProblemLanguageResultExecution timeMemory
569188jeroenodbFortune Telling 2 (JOI14_fortune_telling2)C++17
100 / 100
163 ms11372 KiB
#include "bits/stdc++.h" using namespace std; #define all(x) begin(x),end(x) template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; } template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; } #define debug(a) cerr << "(" << #a << ": " << a << ")\n"; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> pi; const int mxN = 1e5+1, oo = 1.1e9; struct segtree { int ptwo; vector<int> seg; segtree(){} int& operator[](int i) { return seg[i+ptwo]; } segtree(int nn) { ptwo=1; while(ptwo<nn) ptwo*=2; seg.assign(ptwo*2,oo); } void update(int i, int val) { assert(i>=0 and i<ptwo); i+=ptwo; seg[i] = val; for(i/=2;i>=1;i/=2) { seg[i] = min(seg[2*i],seg[2*i+1]); } } int findLastSmall(int v) { int at=1; while(at<ptwo) { at = at*2 + (seg[at*2+1]<v); } return at-ptwo; } }; template<typename T> struct fenwick { int n; vector<T> fen; fenwick(){} fenwick(int nn) { fen.resize(nn+1); n = nn; } auto sum(int i) { T ans = 0; while(i) { ans+=fen[i]; i&=i-1; } return ans; } auto query(int l, int r) { return sum(r+1)-sum(l); } void update(int i, T val) { ++i; while(i<=n) { fen[i]+=val; i+= i&(-i); } } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n,k; cin >> n >> k; segtree seg(k+1); vector<array<int,2>> ab(n); for(auto& [a,b] : ab) cin >> a >> b; for(int i=1;i<=k;++i) { int t; cin >> t; seg.update(i,t); } vi ord(k); iota(all(ord),1); sort(all(ord),[&](int i, int j) {return seg[i]<seg[j];}); sort(all(ab),[&](auto i, auto j) {return min(i[0],i[1])<min(j[0],j[1]);}); ll ans=0; fenwick<int> fen(k+1); int j=0; for(auto& [a,b] : ab) { bool flip=a>b; if(flip) swap(a,b); while(j<k and seg[ord[j]]<a) { seg.update(ord[j],oo); fen.update(ord[j],1); ++j; } int id = seg.findLastSmall(b); bool par=false; if(id==0) { par = (k-id + !flip - fen.query(id,k))%2; } else { par = (k-id - fen.query(id,k))%2; } if(par) ans+=a; else ans+=b; } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...