oj.uz

Submission #423459

# Submission time Handle Problem Language Result Execution time Memory
423459 2021-06-11T07:15:44 Z 조영욱(#7649) Financial Report (JOI21_financial) C++17
31 / 100
 752 ms 40180 KB 
#include <bits/stdc++.h>
using namespace std;

int arr[300001];
int n,d;

const int sz=524288;
vector<int> pr;
int seg[sz*2];

int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (l>r) {
        return 0;
    }
    if (r<nodel||l>noder) {
        return 0;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return max(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}

void update(int i,int val) {
    i+=sz;
    seg[i]=max(seg[i],val);
    while (i>1) {
        i/=2;
        seg[i]=max(seg[i*2],seg[i*2+1]);
    }
}

int le[300001];
int ri[300001];
vector<int> pos[300000];
int lim[300001];
int dp[300001];

int main(void) {
    scanf("%d %d",&n,&d);
    for(int i=1;i<=n;i++) {
        scanf("%d",&arr[i]);
        pr.push_back(arr[i]);
    }
    sort(pr.begin(),pr.end());
    pr.erase(unique(pr.begin(),pr.end()),pr.end());
    le[0]=1;
    for(int i=1;i<=n;i++) {
        arr[i]=lower_bound(pr.begin(),pr.end(),arr[i])-pr.begin();
        pos[arr[i]].push_back(i);
        le[i]=i+1;
        ri[i]=i;
    }
    set<int> s;
    int ret=0;
    for(int i=pr.size()-1;i>=0;i--) {
        //printf("%d\n",s.size());
        /*printf(".");
        for(auto now:s) {
            printf("%d ",now);
        }
        printf("\n");*/
        for(int j=0;j<pos[i].size();j++) {
            int now=pos[i][j];
            auto iter=s.lower_bound(now+d);
            if (iter!=s.end())
                lim[now]=(*iter);
            else
                lim[now]=n;
            //printf("%d %d %d\n",now+1,lim[now],sum(now+1,lim[now]));
            dp[now]=sum(now+1,lim[now])+1;
            ret=max(ret,dp[now]);
        }
        for(int j=0;j<pos[i].size();j++) {
            int now=pos[i][j];
            update(now,dp[now]);
            //printf("%d %d\n",now,dp[now]);
            if (le[now-1]!=now&&le[now+1]!=now+2) {
                int lm=le[now-1];
                ri[le[now-1]]=ri[now+1];
                le[ri[now+1]]=le[now-1];
                if (ri[lm]-lm+1>=d) {
                    s.insert(lm+d-1);
                }
            }
            else if (le[now-1]!=now) {
                int lm=le[now-1];
                ri[lm]=now;
                le[now]=now;
                ri[now]=now;
                if (ri[lm]-lm+1>=d) {
                    s.insert(lm+d-1);
                }
            }
            else if (le[now+1]!=now+2) {
                le[now]=now;
                ri[now]=ri[now+1];
                le[ri[now]]=now;
                if (ri[now]-now+1>=d) {
                    s.insert(now+d-1);
                }
            }
            else {
                le[now]=now;
                ri[now]=now;
                if (d==1) {
                    s.insert(now);
                }
            }
        }
    }
    printf("%d",ret);
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j=0;j<pos[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
Main.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int j=0;j<pos[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
Main.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d %d",&n,&d);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7360 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 4 ms 7420 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 4 ms 7360 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 4 ms 7372 KB Output is correct
13 Correct 4 ms 7372 KB Output is correct
14 Correct 4 ms 7372 KB Output is correct
15 Correct 4 ms 7372 KB Output is correct
16 Correct 4 ms 7372 KB Output is correct
17 Correct 4 ms 7372 KB Output is correct
18 Correct 5 ms 7372 KB Output is correct
19 Correct 4 ms 7372 KB Output is correct
20 Correct 5 ms 7428 KB Output is correct
21 Correct 4 ms 7372 KB Output is correct
22 Correct 4 ms 7396 KB Output is correct
23 Correct 5 ms 7372 KB Output is correct
24 Correct 5 ms 7388 KB Output is correct
25 Correct 5 ms 7372 KB Output is correct
26 Correct 4 ms 7372 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7360 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 4 ms 7420 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 4 ms 7360 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 4 ms 7372 KB Output is correct
13 Correct 4 ms 7372 KB Output is correct
14 Correct 4 ms 7372 KB Output is correct
15 Correct 4 ms 7372 KB Output is correct
16 Correct 4 ms 7372 KB Output is correct
17 Correct 4 ms 7372 KB Output is correct
18 Correct 5 ms 7372 KB Output is correct
19 Correct 4 ms 7372 KB Output is correct
20 Correct 5 ms 7428 KB Output is correct
21 Correct 4 ms 7372 KB Output is correct
22 Correct 4 ms 7396 KB Output is correct
23 Correct 5 ms 7372 KB Output is correct
24 Correct 5 ms 7388 KB Output is correct
25 Correct 5 ms 7372 KB Output is correct
26 Correct 4 ms 7372 KB Output is correct
27 Correct 5 ms 7372 KB Output is correct
28 Incorrect 5 ms 7372 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7360 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 4 ms 7420 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 4 ms 7360 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 4 ms 7372 KB Output is correct
13 Correct 4 ms 7372 KB Output is correct
14 Correct 4 ms 7372 KB Output is correct
15 Correct 4 ms 7372 KB Output is correct
16 Correct 4 ms 7372 KB Output is correct
17 Correct 4 ms 7372 KB Output is correct
18 Correct 5 ms 7372 KB Output is correct
19 Correct 4 ms 7372 KB Output is correct
20 Correct 5 ms 7428 KB Output is correct
21 Correct 4 ms 7372 KB Output is correct
22 Correct 4 ms 7396 KB Output is correct
23 Correct 5 ms 7372 KB Output is correct
24 Correct 5 ms 7388 KB Output is correct
25 Correct 5 ms 7372 KB Output is correct
26 Correct 4 ms 7372 KB Output is correct
27 Correct 5 ms 7372 KB Output is correct
28 Incorrect 5 ms 7372 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 32120 KB Output is correct
2 Correct 243 ms 26608 KB Output is correct
3 Correct 470 ms 26828 KB Output is correct
4 Correct 729 ms 33276 KB Output is correct
5 Correct 486 ms 35384 KB Output is correct
6 Correct 752 ms 34552 KB Output is correct
7 Correct 214 ms 26028 KB Output is correct
8 Correct 348 ms 40180 KB Output is correct
9 Correct 242 ms 36588 KB Output is correct
10 Correct 265 ms 34948 KB Output is correct
11 Correct 383 ms 34624 KB Output is correct
12 Correct 404 ms 34548 KB Output is correct
13 Correct 502 ms 40128 KB Output is correct
14 Correct 617 ms 39972 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 18028 KB Output is correct
2 Correct 253 ms 18184 KB Output is correct
3 Correct 285 ms 18864 KB Output is correct
4 Correct 424 ms 26128 KB Output is correct
5 Correct 378 ms 26032 KB Output is correct
6 Correct 419 ms 26048 KB Output is correct
7 Correct 220 ms 26032 KB Output is correct
8 Correct 221 ms 26068 KB Output is correct
9 Correct 229 ms 25992 KB Output is correct
10 Correct 318 ms 26020 KB Output is correct
11 Correct 432 ms 26152 KB Output is correct
12 Correct 316 ms 26140 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7360 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7372 KB Output is correct
5 Correct 4 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 4 ms 7420 KB Output is correct
8 Correct 5 ms 7500 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 4 ms 7360 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 4 ms 7372 KB Output is correct
13 Correct 4 ms 7372 KB Output is correct
14 Correct 4 ms 7372 KB Output is correct
15 Correct 4 ms 7372 KB Output is correct
16 Correct 4 ms 7372 KB Output is correct
17 Correct 4 ms 7372 KB Output is correct
18 Correct 5 ms 7372 KB Output is correct
19 Correct 4 ms 7372 KB Output is correct
20 Correct 5 ms 7428 KB Output is correct
21 Correct 4 ms 7372 KB Output is correct
22 Correct 4 ms 7396 KB Output is correct
23 Correct 5 ms 7372 KB Output is correct
24 Correct 5 ms 7388 KB Output is correct
25 Correct 5 ms 7372 KB Output is correct
26 Correct 4 ms 7372 KB Output is correct
27 Correct 5 ms 7372 KB Output is correct
28 Incorrect 5 ms 7372 KB Output isn't correct
29 Halted 0 ms 0 KB -