oj.uz

Submission #990374

# Submission time Handle Problem Language Result Execution time Memory
990374 2024-05-30T10:28:53 Z Mihailo Sequence (APIO23_sequence) C++17
19 / 100
 396 ms 75344 KB 
#include "sequence.h"
#include <cassert>
#include <cstdio>
#include <bits/stdc++.h>
#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], 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 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()||sum(1, v1.back()-1)<sum(1, app[i][j]-1)) v1.pb(app[i][j]);
        }
        for(ll j=app[i].size()-1; j>=0; j--) {
            if(v2.empty()||sum(v2.back()+1, n)<sum(app[i][j]+1, n)) v2.pb(app[i][j]);
        }
        p1=0;
        p2=v2.size()-1;
        while(p2>=0) {
            if(p1>=v1.size()||v1[p1]>v2[p2]) {
                p2--;
                continue;
            }
            if(sum(v1[p1], v2[p2])<=0) {
                rez=max(rez, m[v2[p2]]-m[v1[p1]]+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:70: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]
   70 |         for(ll j=0; j<app[i].size(); j++) {
      |                     ~^~~~~~~~~~~~~~
sequence.cpp:74: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]
   74 |         for(ll j=0; j<app[i].size(); j++) {
      |                     ~^~~~~~~~~~~~~~
sequence.cpp:77: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]
   77 |         for(ll j=0; j<app[i].size(); j++) {
      |                     ~^~~~~~~~~~~~~~
sequence.cpp:86:18: 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]
   86 |             if(p1>=v1.size()||v1[p1]>v2[p2]) {
      |                ~~^~~~~~~~~~~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 2 ms 17028 KB Output is correct
4 Correct 2 ms 16984 KB Output is correct
5 Incorrect 2 ms 16988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 2 ms 17028 KB Output is correct
4 Correct 2 ms 16984 KB Output is correct
5 Incorrect 2 ms 16988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 355 ms 74324 KB Output is correct
3 Correct 346 ms 74416 KB Output is correct
4 Correct 353 ms 65136 KB Output is correct
5 Correct 347 ms 75092 KB Output is correct
6 Correct 350 ms 75048 KB Output is correct
7 Correct 342 ms 66588 KB Output is correct
8 Correct 340 ms 67664 KB Output is correct
9 Correct 366 ms 67148 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 396 ms 73468 KB Output is correct
3 Correct 389 ms 69368 KB Output is correct
4 Correct 390 ms 68392 KB Output is correct
5 Correct 394 ms 73276 KB Output is correct
6 Correct 376 ms 66488 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 75344 KB Output is correct
2 Correct 375 ms 75092 KB Output is correct
3 Correct 380 ms 75144 KB Output is correct
4 Correct 379 ms 75092 KB Output is correct
5 Incorrect 356 ms 75008 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 2 ms 17028 KB Output is correct
4 Correct 2 ms 16984 KB Output is correct
5 Incorrect 2 ms 16988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 2 ms 17028 KB Output is correct
4 Correct 2 ms 16984 KB Output is correct
5 Incorrect 2 ms 16988 KB Output isn't correct
6 Halted 0 ms 0 KB -