oj.uz

Submission #172847

# Submission time Handle Problem Language Result Execution time Memory
172847 2020-01-02T16:45:32 Z Swan Money (IZhO17_money) C++14
100 / 100
 299 ms 27024 KB 
#include <bits/stdc++.h>
#define stop system("pause")
#define stop2 char o; cin >> o
#define INP freopen("pcb.in","r",stdin)
#define OUTP freopen ("pcb.out","w",stdout)
using namespace std;

const int maxn = 1e6+2;

vector<int> v;
int dp[maxn];
int bit[maxn];

namespace fen{
    int bit[maxn];
    void upd(int id,int x){
        while(id < maxn){
            bit[id]+=x;
            id|=id+1;
        }
    }
    int sum(int x){
        int res = 0;
        while(x>=0){
            res+=bit[x];
            x&=x+1;x--;
        }
        return res;
    }
    int segm(int l,int r){
        int ans = sum(r);
        if(l)ans-=sum(l-1);
        return ans;
    }
}

main(){
    ios_base::sync_with_stdio(0);
    int n; cin >> n;
    vector<pair<int,int> > qwe;
    int last = -1;
    int cnt = 0;
    for(int i(0); i < n;i++){
        int x; cin >> x;
        v.push_back(x);
        if(x!=last && last!=-1){
            qwe.push_back({last,cnt});
            cnt = 0;
        }else if(last == -1){
            last = x;
            cnt = 0;
        }
        cnt++;
    }
    dp[0] = 1;
    int l = 0;
    for(int i(1);i < n;i++){
        if(v[i] < v[i-1]){
            for(int z(l); z < i;z++)fen::upd(v[z],1);
            l = i;
            dp[i] = dp[i-1]+1;
            continue;
        }
        while(1){
            if(v[i]-v[l]>1){
                int kek = fen::segm(v[l]+1,v[i]-1);
                if(kek){
                    fen::upd(v[l],1);
                    l++;
                }else break;
            }else break;
        }
        dp[i] = dp[l-1]+1;
    }
    cout << dp[n-1];
}
/*
6
1 2 3 4
*/

Compilation message

money.cpp:37:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 504 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 504 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 2 ms 632 KB Output is correct
22 Correct 2 ms 380 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 10 ms 376 KB Output is correct
25 Correct 2 ms 504 KB Output is correct
26 Correct 1 ms 632 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 504 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 2 ms 632 KB Output is correct
22 Correct 2 ms 380 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 10 ms 376 KB Output is correct
25 Correct 2 ms 504 KB Output is correct
26 Correct 1 ms 632 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 3 ms 376 KB Output is correct
29 Correct 3 ms 376 KB Output is correct
30 Correct 1 ms 376 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 504 KB Output is correct
33 Correct 3 ms 504 KB Output is correct
34 Correct 2 ms 504 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 424 KB Output is correct
37 Correct 3 ms 1532 KB Output is correct
38 Correct 3 ms 1656 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 2 ms 504 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 504 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 3 ms 376 KB Output is correct
21 Correct 2 ms 632 KB Output is correct
22 Correct 2 ms 380 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 10 ms 376 KB Output is correct
25 Correct 2 ms 504 KB Output is correct
26 Correct 1 ms 632 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 3 ms 376 KB Output is correct
29 Correct 3 ms 376 KB Output is correct
30 Correct 1 ms 376 KB Output is correct
31 Correct 2 ms 376 KB Output is correct
32 Correct 2 ms 504 KB Output is correct
33 Correct 3 ms 504 KB Output is correct
34 Correct 2 ms 504 KB Output is correct
35 Correct 2 ms 376 KB Output is correct
36 Correct 2 ms 424 KB Output is correct
37 Correct 3 ms 1532 KB Output is correct
38 Correct 3 ms 1656 KB Output is correct
39 Correct 96 ms 10704 KB Output is correct
40 Correct 163 ms 17792 KB Output is correct
41 Correct 83 ms 8664 KB Output is correct
42 Correct 74 ms 8332 KB Output is correct
43 Correct 52 ms 6240 KB Output is correct
44 Correct 204 ms 22324 KB Output is correct
45 Correct 198 ms 21792 KB Output is correct
46 Correct 200 ms 22208 KB Output is correct
47 Correct 179 ms 19264 KB Output is correct
48 Correct 196 ms 20552 KB Output is correct
49 Correct 218 ms 26204 KB Output is correct
50 Correct 299 ms 25684 KB Output is correct
51 Correct 219 ms 26388 KB Output is correct
52 Correct 227 ms 25588 KB Output is correct
53 Correct 221 ms 25864 KB Output is correct
54 Correct 235 ms 25604 KB Output is correct
55 Correct 229 ms 27024 KB Output is correct
56 Correct 231 ms 26816 KB Output is correct
57 Correct 228 ms 26916 KB Output is correct
58 Correct 230 ms 26896 KB Output is correct
59 Correct 224 ms 26908 KB Output is correct
60 Correct 223 ms 26884 KB Output is correct
61 Correct 254 ms 26832 KB Output is correct
62 Correct 257 ms 26896 KB Output is correct