Submission #940461

#TimeUsernameProblemLanguageResultExecution timeMemory
940461a_l_i_r_e_z_aFortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
1 ms4440 KiB
// In the name of God // Hope is last to die #include <bits/stdc++.h> using namespace std; // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2") typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define pb push_back // #define int long long #define S second #define F first #define mp make_pair #define smax(x, y) (x) = max((x), (y)) #define smin(x, y) (x) = min((x), (y)) #define all(x) (x).begin(), (x).end() const int maxn = 2e5 + 5, lg = 19; const int inf = 1e9 + 7; int n, q, rmq[maxn][lg], fen[maxn]; pii a[maxn], b[maxn]; bool cmp(pii x, pii y){ return max(x.F, x.S) > max(y.F, y.S); } void upd(int i){ for(i++; i <= q; i += i & -i) fen[i] += 1; } int get_(int i){ int res = 0; for(i++; i; i &= i - 1) res += fen[i]; return res; } int get(int i){ return get_(q - 1) - get_(i); } int get_rmq(int l, int r){ int bit = 31 - __builtin_clz(r - l); return max(rmq[l][bit], rmq[r - (1ll << bit)][bit]); } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for(int i = 0; i < n ; i++) cin >> a[i].F >> a[i].S; sort(a, a + n, cmp); for(int i = 0; i < q; i++){ cin >> b[i].F; b[i].S = i; } sort(b, b + q); for(int i = q - 1; i >= 0; i--){ rmq[i][0] = b[i].S; for(int bit = 1; bit < lg; bit++){ rmq[i][bit] = rmq[i][bit - 1]; if(i + (1ll << (bit - 1)) < n){ smax(rmq[i][bit], rmq[i + (1ll << (bit - 1))][bit - 1]); } } } int cur = q - 1; ll ans = 0; for(int i = 0; i < n; i++){ int mn = min(a[i].F, a[i].S), mx = a[i].F + a[i].S - mn; while(cur >= 0 && b[cur].F >= mx) upd(b[cur--].S); int j = lower_bound(b, b + q, mp(mn, 0)) - b; int k = lower_bound(b, b + q, mp(mx, 0)) - b; // cout << i << ' ' << a[i].F << ' ' << a[i].S << ' ' << j << ' ' << k << '\n'; if(j == q || b[j].F >= mx){ int x = get(-1); // cout << x << '\n'; if(x % 2) ans += a[i].S; else ans += a[i].F; } else{ int g = get_rmq(j, k); int x = get(g); if(x % 2) ans += mn; else ans += mx; } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...