oj.uz

Submission #13655

# Submission time Handle Problem Language Result Execution time Memory
13655 2015-02-27T06:22:43 Z gs14004 Fortune Telling 2 (JOI14_fortune_telling2) C++14
4 / 100
 2000 ms 11336 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int,int> pi;

vector<int> v;
int n,k;

int a[200005], b[200005], q[200005];
bool flip[200005];

struct rmq{
    int tree[1050000], lim;
    void init(int n){
        for(lim = 1; lim <= n; lim <<= 1);
        memset(tree,-1,sizeof(tree));
    }
    void add(int x, int v){
        if(x < 0) return;
        x += lim;
        tree[x] = v;
        while(x>1){
            x >>= 1;
            tree[x] = max(tree[2*x],tree[2*x+1]);
        }
    }
    int q(int s, int e){
        s += lim;
        e += lim;
        int r = -1;
        while(s < e){
            if(s%2 == 1) r = max(r,tree[s++]);
            if(e%2 == 0) r = max(r,tree[e--]);
            s >>= 1;
            e >>= 1;
        }
        if(s == e) r = max(r,tree[s]);
        return r;
    }
}rmq;

struct bit{
    int tree[400005], lim;
    void init(int n){
        lim = n+2;
    }
    void add(int x){
        x+=2;
        while(x <= lim){
            tree[x]++;
            x += x & -x;
        }
    }
    int sum(int x){
        x+=2;
        int r = 0;
        while(x){
            r += tree[x];
            x -= x & -x;
        }
        return r;
    }
}bit;

void input(){
    scanf("%d %d",&n,&k);
    for (int i=0; i<n; i++) {
        scanf("%d %d",&a[i],&b[i]);
        if(a[i] > b[i]){
            swap(a[i],b[i]);
            flip[i] = 1;
        }
        v.push_back(a[i]);
        v.push_back(b[i]);
    }
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end()) - v.begin());
    for (int i=0; i<n; i++) {
        a[i] = (int)(lower_bound(v.begin(),v.end(),a[i]) - v.begin());
        b[i] = (int)(lower_bound(v.begin(),v.end(),b[i]) - v.begin());
    }
    for (int i=0; i<k; i++) {
        scanf("%d",&q[i]);
        q[i] = (int)(upper_bound(v.begin(),v.end(),q[i]) - v.begin()) - 1;
    }
}

int table[200005];

int main(){
    input();
    rmq.init(2*n);
    for (int i=0; i<k; i++) {
        rmq.add(q[i],i);
    }
    for (int i=0; i<n; i++) {
        table[i] = rmq.q(a[i],b[i]-1);
    }
    bit.init(2*n);
    for (int i=0; i<k; i++) {
        bit.add(q[i]);
    }
    for (int i=0; i<n; i++) {
        if(table[i] >= 0) flip[i] = 1;
    }
    for (int i=0; i<k; i++) {
        for (int j=0; j<n; j++) {
            if(table[j] < i && b[j] <= q[i]){
                flip[j] ^= 1;
            }
        }
    }
    long long ret = 0;
    for (int i=0; i<n; i++) {
        if(flip[i]) ret += v[b[i]];
        else ret += v[a[i]];
    }
    printf("%lld",ret);
}

Subtask #1
4.0 / 4.0

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

Subtask #2
0.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 10696 KB Output is correct
2 Correct 406 ms 10952 KB Output is correct
3 Correct 882 ms 10952 KB Output is correct
4 Correct 1545 ms 11336 KB Output is correct
5 Correct 1544 ms 11336 KB Output is correct
6 Correct 1532 ms 11336 KB Output is correct
7 Correct 1629 ms 11336 KB Output is correct
8 Correct 1532 ms 11336 KB Output is correct
9 Correct 1508 ms 11336 KB Output is correct
10 Correct 1508 ms 11336 KB Output is correct
11 Correct 1497 ms 11336 KB Output is correct
12 Correct 1506 ms 11336 KB Output is correct
13 Execution timed out 2000 ms 11336 KB Program timed out
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1950 ms 10696 KB Output is correct
2 Execution timed out 2000 ms 11336 KB Program timed out
3 Halted 0 ms 0 KB -