oj.uz

답안 #13655

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13655 2015-02-27T06:22:43 Z gs14004 운세 보기 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -