Submission #12862

#TimeUsernameProblemLanguageResultExecution timeMemory
12862tncks0121Fortune Telling 2 (JOI14_fortune_telling2)C++14
0 / 100
140 ms9688 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <stack> #include <queue> #include <map> #include <set> #include <algorithm> #include <string> #include <functional> #include <vector> #include <numeric> #include <deque> #include <utility> #include <bitset> #include <limits.h> #include <iostream> using namespace std; typedef long long ll; typedef unsigned long long llu; typedef double lf; typedef unsigned int uint; typedef long double llf; typedef pair<int, int> pii; const int N_ = 200500; const int K_ = 200500; const int LEAF = 131072*2; int N, K, A[N_], B[N_]; int T[K_], X[K_], XN; struct state { int s, b; state (int s = (int)1e8, int b = -(int)1e8): s(s), b(b) { } }; state tree[LEAF+LEAF]; state merged (state x, state y) { return state(min(x.s, y.s), max(x.b, y.b)); } void upd (int p, state v) { p += LEAF; tree[p] = merged(tree[p], v); while(p >>= 1) tree[p] = merged(tree[p+p], tree[p+p+1]); } state get (int x, int y) { x += LEAF; y += LEAF; state ret; while(x <= y) { if((x & 1) == 1) ret = merged(ret, tree[x]); if((y & 1) == 0) ret = merged(ret, tree[y]); x = (x+1) >> 1; y = (y-1) >> 1; } return ret; } ll ans; int cntX[N_]; int main() { scanf("%d%d", &N, &K); for(int i = 1; i <= N; i++) scanf("%d%d", A+i, B+i); for(int i = 1; i <= K; i++) scanf("%d", T+i), X[i] = T[i]; sort(X+1, X+K+1); XN = unique(X+1, X+K+1) - (X+1); for(int i = 1; i <= K; i++) { int x = lower_bound(X+1, X+XN+1, T[i]) - X; upd(x, state(i, i)); ++cntX[x]; } for(int i = 1; i <= XN; i++) cntX[i] += cntX[i-1]; for(int i = 1; i <= N; i++) { bool r = true; if(A[i] > B[i]) r = false, swap(A[i], B[i]); int a = upper_bound(X+1, X+XN+1, A[i]-1) - X; int b = upper_bound(X+1, X+XN+1, B[i]-1) - X; state p = get(a, b-1); // I state q = get(b, XN); // J int t; //printf("[%d, %d] / [%d, %d]\n", p.s, p.b, q.s, q.b); if(q.b > p.b && p.b > 0) { // p -> q t = A[i]; }else if(p.b > q.b && q.b > 0) { // q -> p t = B[i]; }else if(p.b - 1 > q.b && p.b > 0) { // p -> p t = B[i]; }else { // q -> .. -> q -> q -> q (원래대로) t = r ^ ((K - cntX[a-1]) % 2 == 1) ? A[i] : B[i]; } ans += t; //printf("%d / %d [%d, %d] / %d [%d, %d]\n", t,a,p.s,p.b,b,q.s,q.b); } // puts(""); printf("%lld\n", ans); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...