oj.uz

Submission #12865

# Submission time Handle Problem Language Result Execution time Memory
12865 2015-01-13T16:11:42 Z tncks0121 Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 444 ms 46240 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) {
    state ret;
    if(x > y || x < 1 || y < 1 || x > XN || y > XN) return ret;
    
    x += LEAF; y += LEAF;
    
    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_];

vector<int> tree2[LEAF+LEAF];

int count2 (vector<int> &a, int v) {
    return (int)a.size() - (upper_bound(a.begin(), a.end(), v-1) - a.begin());
}

int get2 (int x, int y, int v) {
    int ret = 0;
    
    x += LEAF; y += LEAF;
    while(x <= y) {
        if((x & 1) == 1) ret += count2 (tree2[x], v);
        if((y & 1) == 0) ret += count2 (tree2[y], v);
        x = (x + 1) >> 1;
        y = (y - 1) >> 1;
    }
    
    return ret;
}
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));
        tree2[LEAF+i].push_back(x);
        ++cntX[x];
    }
    
    for(int u = LEAF-1; u > 0; u--) {
        vector<int> &c1 = tree2[u+u];
        vector<int> &c2 = tree2[u+u+1];
        vector<int> &nd = tree2[u];
        nd.reserve(c1.size() + c2.size());
        for(int i = 0, j = 0; nd.size() < c1.size() + c2.size(); ) {
            if(i == c1.size()) nd.push_back(c2[j++]);
            else if(j == c2.size()) nd.push_back(c1[i++]);
            else if(c1[i] < c2[j]) nd.push_back(c1[i++]);
            else nd.push_back(c2[j++]);
        }
    }
    
    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;
        
        if(q.b == p.b + 1 && p.b > 0) { // .. -> p -> q
            t = A[i];
        }else if(p.b > q.b && q.b > 0) { // q -> q -> q -> p
            t = B[i];
        }else if(p.b - 1 > q.b && p.b > 0) { // .. -> p -> p
            t = B[i];
        }else if(q.b > p.b && p.b > 0) { // .. -> p -> q -> q -> ..
            t = get2(p.b+1, K, b) % 2 == 1 ? A[i] : B[i];
        }else { // only q
            t = r ^ ((K - cntX[a-1]) % 2 == 1) ? A[i] : B[i];
        }
        
        if(K <= 10) {
            if(!r) swap(A[i], B[i]);
        }
        ans += t;
    }
    
    
    
    printf("%lld\n", ans);
    
    return 0;
}

/*
 1 5
 5 6
 7
 3
 5
 7
 6

 6 4

 */

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21980 KB Output is correct
2 Correct 12 ms 21980 KB Output is correct
3 Correct 4 ms 21980 KB Output is correct
4 Correct 12 ms 21980 KB Output is correct
5 Correct 8 ms 21980 KB Output is correct
6 Correct 4 ms 21980 KB Output is correct
7 Correct 8 ms 21980 KB Output is correct
8 Correct 8 ms 21980 KB Output is correct
9 Correct 4 ms 21980 KB Output is correct
10 Correct 4 ms 21980 KB Output is correct
11 Correct 0 ms 21980 KB Output is correct
12 Correct 12 ms 21980 KB Output is correct
13 Correct 4 ms 21980 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23072 KB Output is correct
2 Correct 44 ms 24324 KB Output is correct
3 Correct 52 ms 25496 KB Output is correct
4 Correct 76 ms 26748 KB Output is correct
5 Correct 76 ms 26748 KB Output is correct
6 Correct 72 ms 26748 KB Output is correct
7 Correct 76 ms 26748 KB Output is correct
8 Correct 56 ms 26748 KB Output is correct
9 Correct 48 ms 26748 KB Output is correct
10 Correct 52 ms 26748 KB Output is correct
11 Correct 64 ms 26748 KB Output is correct
12 Correct 64 ms 26748 KB Output is correct
13 Correct 72 ms 26748 KB Output is correct
14 Correct 100 ms 26748 KB Output is correct
15 Correct 80 ms 26748 KB Output is correct
16 Correct 80 ms 26748 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 46240 KB Output is correct
2 Correct 260 ms 46240 KB Output is correct
3 Correct 300 ms 46240 KB Output is correct
4 Correct 420 ms 46240 KB Output is correct
5 Correct 196 ms 46240 KB Output is correct
6 Correct 408 ms 46240 KB Output is correct
7 Correct 424 ms 46240 KB Output is correct
8 Correct 420 ms 46240 KB Output is correct
9 Correct 396 ms 46240 KB Output is correct
10 Correct 420 ms 46240 KB Output is correct
11 Correct 364 ms 46240 KB Output is correct
12 Correct 412 ms 46240 KB Output is correct
13 Correct 428 ms 46240 KB Output is correct
14 Correct 288 ms 46240 KB Output is correct
15 Correct 308 ms 46240 KB Output is correct
16 Correct 280 ms 46240 KB Output is correct
17 Correct 276 ms 46240 KB Output is correct
18 Correct 312 ms 46240 KB Output is correct
19 Correct 444 ms 46240 KB Output is correct
20 Correct 424 ms 46240 KB Output is correct