oj.uz

Submission #57485

# Submission time Handle Problem Language Result Execution time Memory
57485 2018-07-15T07:20:43 Z 조민규(#2116) Teams (CEOI11_tea) C++11
70 / 100
 2500 ms 32736 KB 
#include <cstdio>
#include <algorithm>
#include <deque>
#include <cstring>
using namespace std;
typedef pair<int,int> pi;

int n;
pi a[1000005];
int up[1000005];
int dp2[1000005];

struct rmq{
    int lim;
    pi tree[2100005];
    void init(int n){
        fill(tree,tree+2100005,pi(-2,-1));
        for(lim = 1; lim <= n; lim <<= 1);
    }
    void add(int x, pi v){
        x += lim;
        tree[x] = max(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 ret(-2,-1);
        while(s < e){
            if(s%2 == 1) ret = max(ret,tree[s++]);
            if(e%2 == 0) ret = max(ret,tree[e--]);
            s >>= 1;
            e >>= 1;
        }
        if(s == e) ret = max(ret,tree[s]);
        return ret;
    }
}rmq;

void track(int x){
    if(x == 0) return;
    track(up[x]);
    printf("%d ",x - up[x]);
    for (int i=up[x]+1; i<=x; i++) {
        printf("%d ",a[i].second);
    }
    puts("");
}

int trial(int x){
    rmq.init(n);
    rmq.add(0,pi(0,0));
    for (int i=1; i<=n; i++) {
        pi t = rmq.q(max(i-x,0),i - a[i].first);
        dp2[i] = t.first + 1;
        up[i] = t.second;
        rmq.add(i,pi(dp2[i],i));
    }
    return dp2[n];
}

int main(){
    scanf("%d",&n);
    for (int i=1; i<=n; i++) {
        scanf("%d",&a[i].first);
        a[i].second = i;
    }
    sort(a+1,a+n+1);
    int t = trial(n);
    printf("%d\n",t);
    int s = 0, e = n;
    while (s != e) {
        int m = (s+e)/2;
        if(trial(m) == t) e = m;
        else s = m+1;
    }
    trial(s);
    track(n);
}

Compilation message

tea.cpp: In function 'int main()':
tea.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
tea.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i].first);
         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 16760 KB Output is correct
2 Correct 41 ms 16760 KB Output is correct
3 Correct 33 ms 16780 KB Output is correct
4 Correct 31 ms 16856 KB Output is correct
5 Correct 34 ms 16968 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 16968 KB Output is correct
2 Correct 36 ms 16984 KB Output is correct
3 Correct 43 ms 16984 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16984 KB Output is correct
2 Correct 47 ms 16984 KB Output is correct
3 Correct 44 ms 17012 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 17140 KB Output is correct
2 Correct 68 ms 17140 KB Output is correct
3 Correct 75 ms 17160 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 17172 KB Output is correct
2 Correct 74 ms 17236 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 18760 KB Output is correct
2 Correct 404 ms 18760 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 19036 KB Output is correct
2 Correct 433 ms 19036 KB Output is correct
3 Correct 472 ms 19036 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2566 ms 28740 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2579 ms 32700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2587 ms 32736 KB Time limit exceeded
2 Halted 0 ms 0 KB -