oj.uz

Submission #52336

# Submission time Handle Problem Language Result Execution time Memory
52336 2018-06-25T12:51:04 Z testtest(#1965) Fortune Telling 2 (JOI14_fortune_telling2) C++11
4 / 100
 3000 ms 17260 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);
    while(N > 1000);
    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
 
 */

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:114:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i == c1.size()) nd.push_back(c2[j++]);
                ~~^~~~~~~~~~~~
fortune_telling2.cpp:115:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             else if(j == c2.size()) nd.push_back(c1[i++]);
                     ~~^~~~~~~~~~~~
fortune_telling2.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &K);
     ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:95:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= N; i++) scanf("%d%d", A+i, B+i);
                                 ~~~~~^~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:96:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= K; i++) scanf("%d", T+i), X[i] = T[i];
                                 ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16904 KB Output is correct
2 Correct 22 ms 17000 KB Output is correct
3 Correct 23 ms 17036 KB Output is correct
4 Correct 24 ms 17036 KB Output is correct
5 Correct 25 ms 17112 KB Output is correct
6 Correct 21 ms 17112 KB Output is correct
7 Correct 23 ms 17112 KB Output is correct
8 Correct 24 ms 17236 KB Output is correct
9 Correct 25 ms 17236 KB Output is correct
10 Correct 22 ms 17236 KB Output is correct
11 Correct 23 ms 17236 KB Output is correct
12 Correct 20 ms 17236 KB Output is correct
13 Correct 26 ms 17260 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16904 KB Output is correct
2 Correct 22 ms 17000 KB Output is correct
3 Correct 23 ms 17036 KB Output is correct
4 Correct 24 ms 17036 KB Output is correct
5 Correct 25 ms 17112 KB Output is correct
6 Correct 21 ms 17112 KB Output is correct
7 Correct 23 ms 17112 KB Output is correct
8 Correct 24 ms 17236 KB Output is correct
9 Correct 25 ms 17236 KB Output is correct
10 Correct 22 ms 17236 KB Output is correct
11 Correct 23 ms 17236 KB Output is correct
12 Correct 20 ms 17236 KB Output is correct
13 Correct 26 ms 17260 KB Output is correct
14 Execution timed out 3025 ms 17260 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16904 KB Output is correct
2 Correct 22 ms 17000 KB Output is correct
3 Correct 23 ms 17036 KB Output is correct
4 Correct 24 ms 17036 KB Output is correct
5 Correct 25 ms 17112 KB Output is correct
6 Correct 21 ms 17112 KB Output is correct
7 Correct 23 ms 17112 KB Output is correct
8 Correct 24 ms 17236 KB Output is correct
9 Correct 25 ms 17236 KB Output is correct
10 Correct 22 ms 17236 KB Output is correct
11 Correct 23 ms 17236 KB Output is correct
12 Correct 20 ms 17236 KB Output is correct
13 Correct 26 ms 17260 KB Output is correct
14 Execution timed out 3025 ms 17260 KB Time limit exceeded
15 Halted 0 ms 0 KB -