oj.uz

Submission #491660

# Submission time Handle Problem Language Result Execution time Memory
491660 2021-12-03T17:51:43 Z Bench0310 Teams (CEOI11_tea) C++17
70 / 100
 2500 ms 43332 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")

using namespace std;
typedef long long ll;

const int N=1000005;
vector<array<int,2>> tree(4*N,{0,0});

void update(int idx,int l,int r,int pos,int x)
{
    if(l==r) tree[idx]={x,pos};
    else
    {
        int m=(l+r)/2;
        if(pos<=m) update(2*idx,l,m,pos,x);
        else update(2*idx+1,m+1,r,pos,x);
        tree[idx]=max(tree[2*idx],tree[2*idx+1]);
    }
}

array<int,2> query(int idx,int l,int r,int ql,int qr)
{
    if(ql>qr) return {-1,0};
    if(l==ql&&r==qr) return tree[idx];
    int m=(l+r)/2;
    return max(query(2*idx,l,m,ql,min(qr,m)),query(2*idx+1,m+1,r,max(ql,m+1),qr));
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<array<int,2>> a(n+1,{0,0});
    for(int i=1;i<=n;i++)
    {
        cin >> a[i][0];
        a[i][1]=i;
    }
    sort(a.begin(),a.end());
    vector<int> p(n+1,0);
    auto go=[&](int lim)->int
    {
        int t=0;
        update(1,0,n,0,0);
        for(int i=1;i<=n;i++)
        {
            auto [x,j]=query(1,0,n,max(0,i-lim),i-a[i][0]);
            if(x==-1) update(1,0,n,i,-1);
            else
            {
                update(1,0,n,i,x+1);
                p[i]=j;
            }
            t=x+1;
        }
        for(int i=1;i<=4*n;i++) tree[i]={-1,0};
        return t;
    };
    int cnt=go(n);
    int l=0,r=n;
    while(l<r-1)
    {
        int m=(l+r)/2;
        if(go(m)==cnt) r=m;
        else l=m;
    }
    cout << cnt << "\n";
    go(r);
    int idx=n;
    while(idx>=1)
    {
        cout << idx-p[idx] << " ";
        for(int i=p[idx]+1;i<=idx;i++) cout << a[i][1] << " \n"[i==idx];
        idx=p[idx];
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 31564 KB Output is correct
2 Correct 13 ms 31504 KB Output is correct
3 Correct 12 ms 31564 KB Output is correct
4 Correct 13 ms 31568 KB Output is correct
5 Correct 14 ms 31612 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31564 KB Output is correct
2 Correct 13 ms 31564 KB Output is correct
3 Correct 15 ms 31564 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31564 KB Output is correct
2 Correct 12 ms 31524 KB Output is correct
3 Correct 12 ms 31564 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31676 KB Output is correct
2 Correct 30 ms 31624 KB Output is correct
3 Correct 30 ms 31692 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31592 KB Output is correct
2 Correct 29 ms 31692 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 32940 KB Output is correct
2 Correct 480 ms 32948 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 33188 KB Output is correct
2 Correct 415 ms 32884 KB Output is correct
3 Correct 534 ms 33088 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2569 ms 40316 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 2577 ms 43332 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 2545 ms 43288 KB Time limit exceeded
2 Halted 0 ms 0 KB -