oj.uz

Submission #990382

# Submission time Handle Problem Language Result Execution time Memory
990382 2024-05-30T10:51:05 Z Mihailo Sequence (APIO23_sequence) C++17
100 / 100
 915 ms 75888 KB 
#include "sequence.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#define pll pair<long long, long long>
#define mp make_pair
#define pb push_back
#define xx first
#define yy second
typedef long long ll;
using namespace std;

struct node{
    ll zbir;
    ll pref;
    ll suf;
    ll sred;
    node(){}
    node(ll x):zbir(x),pref(x),suf(x),sred(x){}
};

ll n, g, a[500100], m[500100], p1, p2;
node tree[2000100];
vector<ll> app[500100];
vector<pll> v1, v2;

void update(ll i, ll x) {
    i+=g;
    tree[i]=node(x);
    i/=2;
    while(i>0) {
        tree[i].zbir=tree[2*i].zbir+tree[2*i+1].zbir;
        tree[i].pref=max(tree[2*i].pref, tree[2*i].zbir+tree[2*i+1].pref);
        tree[i].suf=max(tree[2*i+1].suf, tree[2*i].suf+tree[2*i+1].zbir);
        tree[i].sred=max(max(tree[2*i].sred, tree[2*i+1].sred), tree[2*i].suf+tree[2*i+1].pref);
        i/=2;
    }
}

ll sum(ll l, ll r) {
    if(l>r) return 0;
    l+=g;
    r+=g;
    ll rez=0;
    while(l<=r) {
        if(l%2) {
            rez+=tree[l].zbir;
            l++;
        }
        if(r%2==0) {
            rez+=tree[r].zbir;
            r--;
        }
        l/=2;
        r/=2;
    }
    return rez;
}

ll prefm(ll l, ll r) {
    if(l>r) return 0;
    l+=g;
    r+=g;
    ll rez=0, trez=0;
    while(l<=r) {
        if(l%2) {
            rez=max(rez, trez+tree[l].pref);
            trez+=tree[l].zbir;
            l++;
        }
        if(r%2==0) {
            rez=max(rez, trez+sum(l-g, r-g-1)+tree[r].pref);
            r--;
        }
        l/=2;
        r/=2;
    }
    return rez;
}

ll sufm(ll l, ll r) {
    if(l>r) return 0;
    l+=g;
    r+=g;
    ll rez=0, trez=0;
    while(l<=r) {
        if(l%2) {
            rez=max(rez, trez+sum(l-g+1, r-g)+tree[l].suf);
            l++;
        }
        if(r%2==0) {
            rez=max(rez, trez+tree[r].suf);
            trez+=tree[r].zbir;
            r--;
        }
        l/=2;
        r/=2;
    }
    return rez;
}

ll solve() {
    g=1;
    while(g<n) g*=2;
    g--;
    for(ll i=1; i<=n; i++) {
        app[a[i]].pb(i);
        m[i]=app[a[i]].size();
    }
    ll rez=0;
    for(ll i=1; i<=n; i++) update(i, 1);
    for(ll i=1; i<=n; i++) {
        if(app[i].empty()) continue;
        for(ll j=0; j<app[i].size(); j++) {
            update(app[i][j], 0);
        }
        if(sum(1, n)<0) return rez;
        for(ll j=0; j<app[i].size(); j++) {
            update(app[i][j], -1);
        }
        for(ll j=0; j<app[i].size(); j++) {
            if(v1.empty()||v1.back().yy<prefm(1, app[i][j]-1)) v1.pb(mp(app[i][j], prefm(1, app[i][j]-1)));
        }
        for(ll j=app[i].size()-1; j>=0; j--) {
            if(v2.empty()||v2.back().yy<sufm(app[i][j]+1, n)) v2.pb(mp(app[i][j], sufm(app[i][j]-1, n)));
        }
        p1=0;
        p2=v2.size()-1;
        while(p2>=0) {
            if(p1>=v1.size()||v1[p1].xx>v2[p2].xx) {
                p2--;
                continue;
            }
            if(v1[p1].yy+v2[p2].yy>=sum(1, n)) {
                rez=max(rez, m[v2[p2].xx]-m[v1[p1].xx]+1);
                p2--;
            }
            else p1++;
        }
        v1.clear();
        v2.clear();
    }
    return rez;
}

int sequence(int N, vector<int> A) {
    ll rez=0;
    n=N;
    for(ll i=0; i<N; i++) a[i+1]=A[i];
    rez=solve();
    for(ll i=1; i<=n; i++) {
        app[i].clear();
    }
    for(ll i=0; i<N; i++) a[i+1]=N+1-A[i];
    rez=max(rez, solve());
    for(ll i=1; i<=n; i++) {
        app[i].clear();
    }
    return rez;
}

Compilation message

sequence.cpp: In function 'll solve()':
sequence.cpp:114:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         for(ll j=0; j<app[i].size(); j++) {
      |                     ~^~~~~~~~~~~~~~
sequence.cpp:118:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(ll j=0; j<app[i].size(); j++) {
      |                     ~^~~~~~~~~~~~~~
sequence.cpp:121:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for(ll j=0; j<app[i].size(); j++) {
      |                     ~^~~~~~~~~~~~~~
sequence.cpp:130:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |             if(p1>=v1.size()||v1[p1].xx>v2[p2].xx) {
      |                ~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 2 ms 17024 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 17020 KB Output is correct
9 Correct 2 ms 17028 KB Output is correct
10 Correct 2 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 2 ms 16988 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 2 ms 17024 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 17020 KB Output is correct
9 Correct 2 ms 17028 KB Output is correct
10 Correct 2 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 2 ms 16988 KB Output is correct
13 Correct 4 ms 16988 KB Output is correct
14 Correct 4 ms 16992 KB Output is correct
15 Correct 4 ms 16988 KB Output is correct
16 Correct 5 ms 16988 KB Output is correct
17 Correct 4 ms 16996 KB Output is correct
18 Correct 3 ms 16996 KB Output is correct
19 Correct 4 ms 16988 KB Output is correct
20 Correct 4 ms 16996 KB Output is correct
21 Correct 4 ms 16996 KB Output is correct
22 Correct 4 ms 16992 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 532 ms 74320 KB Output is correct
3 Correct 543 ms 74332 KB Output is correct
4 Correct 508 ms 65140 KB Output is correct
5 Correct 534 ms 75012 KB Output is correct
6 Correct 525 ms 74900 KB Output is correct
7 Correct 496 ms 66492 KB Output is correct
8 Correct 491 ms 67664 KB Output is correct
9 Correct 551 ms 67092 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16988 KB Output is correct
2 Correct 569 ms 71860 KB Output is correct
3 Correct 568 ms 70340 KB Output is correct
4 Correct 599 ms 70404 KB Output is correct
5 Correct 569 ms 73096 KB Output is correct
6 Correct 550 ms 66548 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 762 ms 75220 KB Output is correct
2 Correct 831 ms 75344 KB Output is correct
3 Correct 824 ms 75164 KB Output is correct
4 Correct 766 ms 75248 KB Output is correct
5 Correct 653 ms 75032 KB Output is correct
6 Correct 654 ms 75092 KB Output is correct
7 Correct 580 ms 72472 KB Output is correct
8 Correct 556 ms 72916 KB Output is correct

Subtask #6
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 2 ms 17024 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 17020 KB Output is correct
9 Correct 2 ms 17028 KB Output is correct
10 Correct 2 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 2 ms 16988 KB Output is correct
13 Correct 4 ms 16988 KB Output is correct
14 Correct 4 ms 16992 KB Output is correct
15 Correct 4 ms 16988 KB Output is correct
16 Correct 5 ms 16988 KB Output is correct
17 Correct 4 ms 16996 KB Output is correct
18 Correct 3 ms 16996 KB Output is correct
19 Correct 4 ms 16988 KB Output is correct
20 Correct 4 ms 16996 KB Output is correct
21 Correct 4 ms 16996 KB Output is correct
22 Correct 4 ms 16992 KB Output is correct
23 Correct 111 ms 26192 KB Output is correct
24 Correct 106 ms 26192 KB Output is correct
25 Correct 110 ms 26188 KB Output is correct
26 Correct 119 ms 26128 KB Output is correct
27 Correct 115 ms 26200 KB Output is correct
28 Correct 110 ms 26192 KB Output is correct
29 Correct 87 ms 25432 KB Output is correct
30 Correct 83 ms 25224 KB Output is correct
31 Correct 115 ms 26036 KB Output is correct
32 Correct 72 ms 26456 KB Output is correct
33 Correct 117 ms 26192 KB Output is correct
34 Correct 104 ms 26320 KB Output is correct
35 Correct 105 ms 26192 KB Output is correct
36 Correct 107 ms 26532 KB Output is correct
37 Correct 104 ms 26452 KB Output is correct
38 Correct 102 ms 26448 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 2 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 2 ms 17024 KB Output is correct
7 Correct 2 ms 16988 KB Output is correct
8 Correct 2 ms 17020 KB Output is correct
9 Correct 2 ms 17028 KB Output is correct
10 Correct 2 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 2 ms 16988 KB Output is correct
13 Correct 4 ms 16988 KB Output is correct
14 Correct 4 ms 16992 KB Output is correct
15 Correct 4 ms 16988 KB Output is correct
16 Correct 5 ms 16988 KB Output is correct
17 Correct 4 ms 16996 KB Output is correct
18 Correct 3 ms 16996 KB Output is correct
19 Correct 4 ms 16988 KB Output is correct
20 Correct 4 ms 16996 KB Output is correct
21 Correct 4 ms 16996 KB Output is correct
22 Correct 4 ms 16992 KB Output is correct
23 Correct 532 ms 74320 KB Output is correct
24 Correct 543 ms 74332 KB Output is correct
25 Correct 508 ms 65140 KB Output is correct
26 Correct 534 ms 75012 KB Output is correct
27 Correct 525 ms 74900 KB Output is correct
28 Correct 496 ms 66492 KB Output is correct
29 Correct 491 ms 67664 KB Output is correct
30 Correct 551 ms 67092 KB Output is correct
31 Correct 569 ms 71860 KB Output is correct
32 Correct 568 ms 70340 KB Output is correct
33 Correct 599 ms 70404 KB Output is correct
34 Correct 569 ms 73096 KB Output is correct
35 Correct 550 ms 66548 KB Output is correct
36 Correct 762 ms 75220 KB Output is correct
37 Correct 831 ms 75344 KB Output is correct
38 Correct 824 ms 75164 KB Output is correct
39 Correct 766 ms 75248 KB Output is correct
40 Correct 653 ms 75032 KB Output is correct
41 Correct 654 ms 75092 KB Output is correct
42 Correct 580 ms 72472 KB Output is correct
43 Correct 556 ms 72916 KB Output is correct
44 Correct 111 ms 26192 KB Output is correct
45 Correct 106 ms 26192 KB Output is correct
46 Correct 110 ms 26188 KB Output is correct
47 Correct 119 ms 26128 KB Output is correct
48 Correct 115 ms 26200 KB Output is correct
49 Correct 110 ms 26192 KB Output is correct
50 Correct 87 ms 25432 KB Output is correct
51 Correct 83 ms 25224 KB Output is correct
52 Correct 115 ms 26036 KB Output is correct
53 Correct 72 ms 26456 KB Output is correct
54 Correct 117 ms 26192 KB Output is correct
55 Correct 104 ms 26320 KB Output is correct
56 Correct 105 ms 26192 KB Output is correct
57 Correct 107 ms 26532 KB Output is correct
58 Correct 104 ms 26452 KB Output is correct
59 Correct 102 ms 26448 KB Output is correct
60 Correct 898 ms 74324 KB Output is correct
61 Correct 903 ms 74324 KB Output is correct
62 Correct 915 ms 74324 KB Output is correct
63 Correct 897 ms 70736 KB Output is correct
64 Correct 885 ms 70724 KB Output is correct
65 Correct 896 ms 70540 KB Output is correct
66 Correct 591 ms 68128 KB Output is correct
67 Correct 617 ms 68464 KB Output is correct
68 Correct 817 ms 70584 KB Output is correct
69 Correct 524 ms 75088 KB Output is correct
70 Correct 878 ms 74440 KB Output is correct
71 Correct 913 ms 74820 KB Output is correct
72 Correct 880 ms 74696 KB Output is correct
73 Correct 903 ms 75204 KB Output is correct
74 Correct 859 ms 75220 KB Output is correct
75 Correct 887 ms 75888 KB Output is correct