oj.uz

Submission #14353

# Submission time Handle Problem Language Result Execution time Memory
14353 2015-05-12T11:04:35 Z gs14004 전선 연결하기 (GA9_wire) C++14
0 / 100
 12 ms 39884 KB 
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
typedef pair<int,int> pi;

int n,a[600005];
int lp[300005], rp[300005];

struct rmaxq{
    int lim;
    pi tree[2100000];
    void init(int n){
        for(lim = 1; lim <= n; lim <<= 1);
    }
    void add(int x, pi v){
        x += lim;
        tree[x] = v;
        while(x > 1){
            x >>= 1;
            tree[x] = max(tree[2*x],tree[2*x+1]);
        }
    }
    pi q(int s, int e){
        s += lim;
        e += lim;
        pi r(0,0);
        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;
    }
}rmaxq;

struct rminq{
    int lim;
    pi tree[2100000];
    void init(int n){
        fill(tree,tree+2100000,pi(1e9,1e9));
        for(lim = 1; lim <= n; lim <<= 1);
    }
    void add(int x, pi v){
        x += lim;
        tree[x] = v;
        while(x > 1){
            x >>= 1;
            tree[x] = min(tree[2*x],tree[2*x+1]);
        }
    }
    pi q(int s, int e){
        s += lim;
        e += lim;
        pi r(1e9,1e9);
        while(s < e){
            if(s%2 == 1) r = min(r,tree[s++]);
            if(e%2 == 0) r = min(r,tree[e--]);
            s >>= 1;
            e >>= 1;
        }
        if(s == e) r = min(r,tree[s]);
        return r;
    }
}rminq;

int lab[300005];

void dfs(int x, int l){
    lab[x] = l;
    rmaxq.add(lp[x],pi(-1,-1));
    rminq.add(rp[x],pi(1e9,1e9));
    while (1) {
        pi t = rmaxq.q(lp[x]+1,rp[x]-1);
        if(t.first > rp[x]){
            dfs(t.second,3-l);
        }
        else break;
    }
    while (1) {
        pi t = rminq.q(lp[x]+1,rp[x]-1);
        if(t.first < lp[x]){
            dfs(t.second,3-l);
        }
        else break;
    }
}

vector<pi> v1, v2;

bool eval(vector<pi> &v){
    sort(v.begin(),v.end());
    int rend = 0;
    for (auto &i : v){
        if(rend > i.second){
            rend = i.second;
        }
        else{
            if(rend > i.first) return 0;
            rend = i.second;
        }
    }
    return 1;
}

int main(){
    scanf("%d",&n);
    for (int i=1; i<=2*n; i++) {
        scanf("%d",&a[i]);
        if(lp[a[i]] == 0) lp[a[i]] = i;
        else rp[a[i]] = i;
    }
    rmaxq.init(2*n);
    rminq.init(2*n);
    for (int i=1; i<=n; i++){
        rmaxq.add(lp[i],pi(rp[i],i));
        rminq.add(rp[i],pi(lp[i],i));
    }
    for (int i=1; i<=n; i++){
        if(!lab[i]) dfs(i,1);
    }
    for (int i=1; i<=n; i++) {
        if(lab[i] == 1){
            v1.push_back(pi(lp[i],rp[i]));
        }
        else{
            v2.push_back(pi(lp[i],rp[i]));
        }
    }
    if(!eval(v1) || !eval(v2)){
        puts("IMPOSSIBLE");
        return 0;
    }
    for (int i=1; i<=2*n; i++) {
        putchar(lab[a[i]] == 1 ? '^' : 'v');
    }
}

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 39884 KB Output is correct
2 Correct 6 ms 39884 KB Output is correct
3 Correct 6 ms 39884 KB Output is correct
4 Correct 6 ms 39884 KB Output is correct
5 Correct 3 ms 39884 KB Output is correct
6 Correct 9 ms 39884 KB Output is correct
7 Correct 8 ms 39884 KB Output is correct
8 Correct 8 ms 39884 KB Output is correct
9 Correct 8 ms 39884 KB Output is correct
10 Correct 8 ms 39884 KB Output is correct
11 Correct 8 ms 39884 KB Output is correct
12 Correct 6 ms 39884 KB Output is correct
13 Correct 6 ms 39884 KB Output is correct
14 Correct 8 ms 39884 KB Output is correct
15 Correct 10 ms 39884 KB Output is correct
16 Correct 12 ms 39884 KB Output is correct
17 Correct 8 ms 39884 KB Output is correct
18 Correct 8 ms 39884 KB Output is correct
19 Correct 4 ms 39884 KB Output is correct
20 Correct 12 ms 39884 KB Output is correct
21 Correct 8 ms 39884 KB Output is correct
22 Correct 8 ms 39884 KB Output is correct
23 Correct 9 ms 39884 KB Output is correct
24 Correct 8 ms 39884 KB Output is correct
25 Correct 8 ms 39884 KB Output is correct
26 Correct 9 ms 39884 KB Output is correct
27 Correct 4 ms 39884 KB Output is correct
28 Correct 4 ms 39884 KB Output is correct
29 Correct 8 ms 39884 KB Output is correct
30 Correct 4 ms 39884 KB Output is correct
31 Correct 8 ms 39884 KB Output is correct
32 Correct 6 ms 39884 KB Output is correct
33 Incorrect 8 ms 39884 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 37.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -