oj.uz

Submission #981947

# Submission time Handle Problem Language Result Execution time Memory
981947 2024-05-13T17:02:39 Z vjudge1 Sequence (APIO23_sequence) C++17
0 / 100
 2000 ms 53404 KB 
// hola soy Dember :D
// 31/03/2024

#include <bits/stdc++.h>

#define ll int
#define pll pair<ll,ll>
#define F first
#define S second 
#define Z size()
#define pb push_back
#define bp pop_back
#define fo(x,y,z) for(ll x=y; x<=z; x++)
#define of(x,y,z) for(ll x=y; x>=z; x--)
#define all(n) n.begin(), n.end()
#define arr(x,y,z) x+y, x+y+z

using namespace std;
const int MN=5e5+5;
 
vector<ll> v[MN];
ll L[MN], R[MN];
ll minx[4*MN], maxx[4*MN], lazy[4*MN];
ll a[MN], b[MN], ans=1;

void push(ll i, ll l, ll r){
    if(!lazy[i])return;
    minx[i]+=lazy[i];
    maxx[i]+=lazy[i];
    if(l!=r){
        lazy[i*2]+=lazy[i];
        lazy[i*2+1]+=lazy[i];
    }
    lazy[i]=0;
    return;
}//
 
void bld(ll i, ll l, ll r, ll xd, ll zd, ll p){
    push(i, l, r);
    if(l>zd || r<xd)return;
    if (xd<=l && r<=zd) {
        lazy[i]=p;
        push(i, l, r);
        return;
    }
    
    bld(2*i, l, (l+r)/2, xd, zd, p);
    bld(2*i+1, (l+r)/2+1, r, xd, zd, p);
    
    minx[i]=min(minx[2*i], minx[2*i+1]);
    maxx[i]=max(maxx[2*i], maxx[2*i+1]);
    return;
}//
 
ll qmin(ll i, ll l, ll r, ll xd, ll zd){
    push(i, l, r);
    if(l>zd || r<xd)return 1e9;
    if(xd<=l && r<=zd)return minx[i];
    
    return min(qmin(2*i, l, (l+r)/2, xd, zd), qmin(2*i+1, (l+r)/2+1, r, xd, zd));
}//
ll qmax(ll i, ll l, ll r, ll xd, ll zd) {
    push(i, l, r);
    if(l>zd || r<xd)return -1e9;
    if(xd<=l && r<=zd)return maxx[i];
    
    return max(qmax(2*i, l, (l+r)/2, xd, zd), qmax(2*i+1, (l+r)/2+1, r, xd, zd));
}//
ll res;
void BB(ll l, ll r, ll zd, ll p){
    if(l>r)return;
    
    if (zd+(p+1)*2>=a[(l+r)/2]) {
        res=(l+r)/2;
        BB(l,(l+r)/2-1,zd,p);
        return;
    } 
    BB((l+r)/2, r,zd,p);
    return;
}
 
int sequence(int n, vector<int> A) {
    fo(i,1,n)v[A[i-1]].push_back(i),bld(1, 0, n, i, i, -i);
 
    fo(h,1,n){
        ll j=0, k=0;
        a[0]=1e9;
        fo(i,0,v[h].Z-1){
            ll x=v[h][i];
            L[i]=qmin(1, 0, n, 0, x-1);
            R[i]=qmax(1, 0, n, 0, x-1);
            
            ll xd= qmin(1, 0, n, x, n);
            ll zd= qmax(1, 0, n, x, n);
            
            while(j<=i && L[j]>zd || R[j]<xd) {
                if (L[j]+j*2<=a[k]) {
                    k++;
                    a[k]=L[j]+j*2;
                    b[k]=j;
                }
                j++;
            }
            
            if(j>0 && L[j-1]>zd){
                res=0;
                BB(1,k,zd,i);
                if(res)ans=max(ans, i-b[res]+1);
            }
            
            ans=max(ans, i-j+1);
        }
        for(auto u:v[h])bld(1, 0, n, u, n, 2);
    }
    return ans;
}

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:13:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 | #define fo(x,y,z) for(ll x=y; x<=z; x++)
......
   88 |         fo(i,0,v[h].Z-1){
      |            ~~~~~~~~~~~~         
sequence.cpp:88:9: note: in expansion of macro 'fo'
   88 |         fo(i,0,v[h].Z-1){
      |         ^~
sequence.cpp:96:24: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   96 |             while(j<=i && L[j]>zd || R[j]<xd) {
      |                   ~~~~~^~~~~~~~~~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 22616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 22616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 22616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 21 ms 45912 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 53404 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 22616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2037 ms 22616 KB Time limit exceeded
2 Halted 0 ms 0 KB -