oj.uz

Submission #12862

# Submission time Handle Problem Language Result Execution time Memory
12862 2015-01-13T15:08:13 Z tncks0121 Fortune Telling 2 (JOI14_fortune_telling2) C++14
0 / 100
 140 ms 9688 KB 
#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;
}

Subtask #1
0.0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 9688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 9688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 9688 KB Output isn't correct
2 Halted 0 ms 0 KB -