oj.uz

Submission #423456

# Submission time Handle Problem Language Result Execution time Memory
423456 2021-06-11T07:06:50 Z 조영욱(#7649) Financial Report (JOI21_financial) C++17
31 / 100
 709 ms 40128 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);
            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];
                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 5 ms 7372 KB Output is correct
2 Correct 6 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 4 ms 7372 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 5 ms 7372 KB Output is correct
13 Correct 5 ms 7372 KB Output is correct
14 Correct 4 ms 7308 KB Output is correct
15 Correct 4 ms 7372 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Correct 5 ms 7372 KB Output is correct
18 Correct 5 ms 7428 KB Output is correct
19 Correct 5 ms 7372 KB Output is correct
20 Correct 5 ms 7372 KB Output is correct
21 Correct 5 ms 7500 KB Output is correct
22 Correct 4 ms 7372 KB Output is correct
23 Correct 4 ms 7416 KB Output is correct
24 Correct 4 ms 7372 KB Output is correct
25 Correct 4 ms 7372 KB Output is correct
26 Correct 5 ms 7372 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 6 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 4 ms 7372 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 5 ms 7372 KB Output is correct
13 Correct 5 ms 7372 KB Output is correct
14 Correct 4 ms 7308 KB Output is correct
15 Correct 4 ms 7372 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Correct 5 ms 7372 KB Output is correct
18 Correct 5 ms 7428 KB Output is correct
19 Correct 5 ms 7372 KB Output is correct
20 Correct 5 ms 7372 KB Output is correct
21 Correct 5 ms 7500 KB Output is correct
22 Correct 4 ms 7372 KB Output is correct
23 Correct 4 ms 7416 KB Output is correct
24 Correct 4 ms 7372 KB Output is correct
25 Correct 4 ms 7372 KB Output is correct
26 Correct 5 ms 7372 KB Output is correct
27 Correct 5 ms 7372 KB Output is correct
28 Incorrect 4 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 5 ms 7372 KB Output is correct
2 Correct 6 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 4 ms 7372 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 5 ms 7372 KB Output is correct
13 Correct 5 ms 7372 KB Output is correct
14 Correct 4 ms 7308 KB Output is correct
15 Correct 4 ms 7372 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Correct 5 ms 7372 KB Output is correct
18 Correct 5 ms 7428 KB Output is correct
19 Correct 5 ms 7372 KB Output is correct
20 Correct 5 ms 7372 KB Output is correct
21 Correct 5 ms 7500 KB Output is correct
22 Correct 4 ms 7372 KB Output is correct
23 Correct 4 ms 7416 KB Output is correct
24 Correct 4 ms 7372 KB Output is correct
25 Correct 4 ms 7372 KB Output is correct
26 Correct 5 ms 7372 KB Output is correct
27 Correct 5 ms 7372 KB Output is correct
28 Incorrect 4 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 271 ms 32028 KB Output is correct
2 Correct 247 ms 26932 KB Output is correct
3 Correct 451 ms 27136 KB Output is correct
4 Correct 639 ms 33552 KB Output is correct
5 Correct 452 ms 35632 KB Output is correct
6 Correct 687 ms 34980 KB Output is correct
7 Correct 217 ms 26028 KB Output is correct
8 Correct 341 ms 40128 KB Output is correct
9 Correct 248 ms 36660 KB Output is correct
10 Correct 314 ms 35092 KB Output is correct
11 Correct 399 ms 34924 KB Output is correct
12 Correct 427 ms 34992 KB Output is correct
13 Correct 479 ms 40080 KB Output is correct
14 Correct 709 ms 40012 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 18028 KB Output is correct
2 Correct 258 ms 18220 KB Output is correct
3 Correct 300 ms 18872 KB Output is correct
4 Correct 493 ms 26152 KB Output is correct
5 Correct 387 ms 26152 KB Output is correct
6 Correct 490 ms 26152 KB Output is correct
7 Correct 217 ms 26124 KB Output is correct
8 Correct 243 ms 26036 KB Output is correct
9 Correct 232 ms 25980 KB Output is correct
10 Correct 309 ms 26160 KB Output is correct
11 Correct 391 ms 26164 KB Output is correct
12 Correct 311 ms 26040 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7372 KB Output is correct
2 Correct 6 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 4 ms 7372 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 5 ms 7372 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 5 ms 7372 KB Output is correct
13 Correct 5 ms 7372 KB Output is correct
14 Correct 4 ms 7308 KB Output is correct
15 Correct 4 ms 7372 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Correct 5 ms 7372 KB Output is correct
18 Correct 5 ms 7428 KB Output is correct
19 Correct 5 ms 7372 KB Output is correct
20 Correct 5 ms 7372 KB Output is correct
21 Correct 5 ms 7500 KB Output is correct
22 Correct 4 ms 7372 KB Output is correct
23 Correct 4 ms 7416 KB Output is correct
24 Correct 4 ms 7372 KB Output is correct
25 Correct 4 ms 7372 KB Output is correct
26 Correct 5 ms 7372 KB Output is correct
27 Correct 5 ms 7372 KB Output is correct
28 Incorrect 4 ms 7372 KB Output isn't correct
29 Halted 0 ms 0 KB -