Submission #1040814

#TimeUsernameProblemLanguageResultExecution timeMemory
1040814minhquaanzFortune Telling 2 (JOI14_fortune_telling2)C++14
100 / 100
286 ms54800 KiB
/*Code by TMQ*/ #include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define ld long double #define task "name" #define ii pair<int, int > #define fi first #define se second #define pb push_back #define em emplace #define all(x) (x).begin(), (x).end() #define sall(x) sort(all(x)) #define rall(x) reverse(all(x)) #define reset(a, x) (memset(a, x, sizeof(a))); #define testcase int tc; cin >> tc; while(tc--) solve(); ll inline gcd(ll a, ll b) { return !b ? abs(a) : gcd(b, a % b); } ll inline lcm(ll a, ll b) { return (a / gcd(a, b) * b); } ///============================================================================ #define BIT(i,mask) ((mask >> (i-1)) & 1) #define DAOBIT(i,mask) ((mask ^ (1<<i-1))) #define OFFBIT(i,mask) ((mask & ~(1 << (i - 1)))) #define ONBIT(i,mask) ((mask | (1 << (i - 1)))) ///============================================================================ const ll mod = 1000000007; const ll mod1 = 998244353; const ll inf = 1000000000000000000 + 10; const ll nmax = 200002; using namespace std; int s[nmax][2]; int a[nmax]; vector<int> t[nmax * 4]; void build(int k, int l, int r) { if (l == r) { t[k] = { a[l] }; return; } int i1 = 0, i2 = 0, id1 = k << 1, id2 = k << 1 | 1, s1, s2, m = (l + r) >> 1; build(id1, l, m); build(id2, m + 1, r); s1 = t[id1].size(); s2 = t[id2].size(); while (i1 != s1 && i2 != s2) if (t[id1][i1] > t[id2][i2]) t[k].pb(t[id2][i2++]); else t[k].pb(t[id1][i1++]); while (i1 != s1) t[k].pb(t[id1][i1++]); while (i2 != s2) t[k].pb(t[id2][i2++]); } pair<int, int> query(int k, int l, int r, int f, int s) { ///cout << '\n' << '\n'; auto it = lower_bound(all(t[k]), min(f, s)); if (it == t[k].end()) { ////cerr << t[k].end() - it << '\n'; return { 0, 0 }; } if (*it >= max(f, s)) { ///cerr << t[k].end() - it << '\n'; return { 0, t[k].end() - it }; } if (l == r) return { 1, 0 }; int m = (l + r) >> 1; auto r2 = query(k << 1 | 1, m + 1, r, f, s); if (r2.fi) return r2; auto r1 = query(k << 1, l, m, f, s); return { r1.fi, r1.se ^ r2.se }; } ll res; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; for (int i = 1; i <= n; i++) cin >> s[i][0] >> s[i][1]; for (int i = 1; i <= k; i++) cin >> a[i]; build(1, 1, k); for (int i = 1; i <= n; i++) { auto w = query(1, 1, k, s[i][0], s[i][1]); ///cerr << w.fi << ' ' << w.se << '\n'; ///cout << '\n'; if (w.fi && s[i][0] < s[i][1]) swap(s[i][0], s[i][1]); res += s[i][w.se & 1]; } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...