Submission #656579

#TimeUsernameProblemLanguageResultExecution timeMemory
656579mouseyFortune Telling 2 (JOI14_fortune_telling2)C++14
4 / 100
3095 ms59392 KiB
#include <bits/stdc++.h> #define ll long long #define vll vector<ll> #define vllp vector<pair<ll, ll> > #define vi vector <int> #define vip vector <pair <int, int> > #define db double #define ld long double #define pdb pair <double, double> #define YES cout<<"YES" #define NO cout<<"NO" #define nl cout<<"\n" #define vv vector <vector <ll> > #define pll pair <ll, ll> #define pi pair <int, int> #define pb push_back #define f first #define s second using namespace std; const ll mod=1e9+7; const ll modx=998244353; const ld eps=1e-9; const ll INF=INT_MAX; const ll INFINF=1e18; const ll N=2e5; int n, q; vip v; void input() { cin >> n >> q; for(int i = 1; i <= n; i++) { int x, y; cin >> x >> y; v.pb({x, y}); } } struct Node{ vi x, y; int lazy, x_max, x_min, y_max, y_min; }; Node st[4*N+5]; void Nodeupdate(int id) { st[id].x.clear(); st[id].y.clear(); for(int i = id*2; i <= id*2+1; i++) { for(auto j: st[i].x) st[id].x.pb(j); for(auto j: st[i].y) st[id].y.pb(j); } st[id].x_max=max(st[id*2].x_max, st[id*2+1].x_max); st[id].y_max=max(st[id*2].y_max, st[id*2+1].y_max); st[id].x_min=min(st[id*2].x_min, st[id*2+1].x_min); st[id].y_min=min(st[id*2].y_min, st[id*2+1].y_min); } void build(int l, int r, int id) { st[id].lazy=0; if(l==r) { st[id].x.clear(); st[id].y.clear(); st[id].x.pb(v[l-1].f); st[id].y.pb(v[l-1].s); st[id].x_max=v[l-1].f; st[id].x_min=v[l-1].f; st[id].y_max=v[l-1].s; st[id].y_min=v[l-1].s; return; } int mid=(l+r)/2; build(l, mid, id*2); build(mid+1, r, id*2+1); Nodeupdate(id); } void Nodeswap(int id) { swap(st[id].x, st[id].y); swap(st[id].x_min, st[id].y_min); swap(st[id].x_max, st[id].y_max); } void push(int id) { st[id*2].lazy^=1; st[id*2+1].lazy^=1; } void update(int l, int r, int id, int val) { // cout << l << " " << r << " " << id << "\n"; // cout << st[id].x_min << " " << st[id].x_max << "\n"; if(st[id].lazy) { Nodeswap(id); if(l!=r) push(id); st[id].lazy=0; } if(st[id].x_min>val) return; else if(st[id].x_max<=val) { Nodeswap(id); if(l!=r) push(id); return; } int mid=(l+r)/2; update(l, mid, id*2, val); update(mid+1, r, id*2+1, val); Nodeupdate(id); } void query() { if(st[1].lazy) Nodeswap(1); for(int i = 0; i < n; i++) v.pb({st[1].x[i], st[1].y[i]}); } void solve() { sort(v.begin(), v.end()); build(1, n, 1); for(int i = 1; i <= q; i++) { int l; cin >> l; update(1, n, 1, l); } v.clear(); query(); ll ans=0; for(auto i: v) ans+=i.f; cout << ans; } signed main() { // auto start_time = chrono::high_resolution_clock::now(); // freopen("SHOPPING.inp", "r", stdin); // freopen("SHOPPING.out", "w", stdout); srand(time(0)); ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t=1; // cin >> t; for(int i = 1; i <= t; i++) { input(); solve(); nl; } // auto end_time = chrono::high_resolution_clock::now(); // double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count(); // cout << "\n[ " << duration << " ms ]\n"; } /* 7 3 4 6 8 2 10 5 1 6 1 1000000000 17 4 1 1000000000 17 1 1 1000000000 17 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...