oj.uz

Submission #1078056

# Submission time Handle Problem Language Result Execution time Memory
1078056 2024-08-27T12:05:57 Z ASN49K Peru (RMI20_peru) C++14
49 / 100
 600 ms 163520 KB 
#include "peru.h"
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
const i64 INF=1e18;
const i64 inf=1e9;
const int mod=1e9+7;
const int BASE=23;
int lsb(int x)
{
    return x&(-x);
}
int add(int x,int y)
{
    return (x+y)%mod;
}
int prod(int x,int y)
{
    return (1LL*x*y)%mod;
}
struct Aint
{
    int n;
    vector<i64>aint,lazy;
    void init(int n)
    {
        this->n=n;
        int aint_size=n;
        while(aint_size!=lsb(aint_size))
        {
            aint_size+=lsb(aint_size);
        }
        aint_size<<=1;
        aint.assign(aint_size+1 , 0);
        lazy.assign(aint_size+1 , 0);
    }
    void add(int nod,i64 val)
    {
        aint[nod]+=val;
        lazy[nod]+=val;
    }
    void push_down(int nod)
    {
        add(nod<<1 , lazy[nod]);
        add(nod<<1|1 , lazy[nod]);
        lazy[nod]=0;
    }
    void update(int nod,int st,int dr,int l,int r,i64 val) {
        if (st > r || dr < l) {
            return;
        }
        if (l <= st && dr <= r)
        {
            add(nod , val);
            return;
        }
        push_down(nod);
        int m=(st+dr)/2;
        update(nod<<1,st,m,l,r,val);
        update(nod<<1|1,m+1,dr,l,r,val);
        aint[nod]=min(aint[nod<<1] , aint[nod<<1|1]);
    }
    i64 query(int nod,int st,int dr,int l,int r)
    {
        if (st > r || dr < l) {
            return INF;
        }
        if (l <= st && dr <= r)
        {
            return aint[nod];
        }
        push_down(nod);
        int m=(st+dr)/2;
        return min(query(nod<<1,st,m,l,r) , query(nod<<1|1,m+1,dr,l,r));
    }
};
int solve(int n, int k, int* v)
{
    vector<int>a(n+2 , 2*inf+1);
    for(int i=1;i<=n;i++)
    {
        a[i]=v[i-1];
    }

    stack<int>sk;
    sk.push(0);
    Aint dp;
    dp.init(n+1);
    dp.update(1,0,n,0,0,a[1]);

    int rez=0;
    for(int i=1;i<=n;i++)
    {
        while(a[i]>=a[sk.top()])
        {
            int r=sk.top()-1;
            sk.pop();
            int l=sk.top();
            dp.update(1,0,n,l,r,a[i]-a[r+1]);
        }
        i64 val=dp.query(1,0,n,max(i-k , 0),i-1);
        rez=prod(rez , BASE);
        rez=add(rez , val%mod);
        dp.update(1,0,n,i,i,val+a[i+1]);
        sk.push(i);
    }
    return rez;
}

Subtask #1
18.0 / 18.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 464 KB Output is correct
15 Correct 226 ms 22320 KB Output is correct
16 Correct 222 ms 22300 KB Output is correct
17 Correct 265 ms 22452 KB Output is correct
18 Correct 237 ms 22356 KB Output is correct
19 Correct 231 ms 22352 KB Output is correct
20 Correct 230 ms 22480 KB Output is correct
21 Correct 235 ms 22344 KB Output is correct
22 Correct 227 ms 22612 KB Output is correct
23 Correct 221 ms 22344 KB Output is correct
24 Correct 218 ms 22484 KB Output is correct
25 Correct 221 ms 22352 KB Output is correct
26 Correct 214 ms 22360 KB Output is correct
27 Correct 223 ms 22212 KB Output is correct
28 Correct 240 ms 22564 KB Output is correct
29 Correct 241 ms 22352 KB Output is correct
30 Correct 231 ms 22268 KB Output is correct
31 Correct 211 ms 22420 KB Output is correct
32 Correct 230 ms 22592 KB Output is correct
33 Correct 218 ms 22348 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 22320 KB Output is correct
2 Correct 222 ms 22300 KB Output is correct
3 Correct 265 ms 22452 KB Output is correct
4 Correct 237 ms 22356 KB Output is correct
5 Correct 231 ms 22352 KB Output is correct
6 Correct 230 ms 22480 KB Output is correct
7 Correct 235 ms 22344 KB Output is correct
8 Correct 227 ms 22612 KB Output is correct
9 Correct 221 ms 22344 KB Output is correct
10 Correct 218 ms 22484 KB Output is correct
11 Correct 221 ms 22352 KB Output is correct
12 Correct 214 ms 22360 KB Output is correct
13 Correct 223 ms 22212 KB Output is correct
14 Correct 240 ms 22564 KB Output is correct
15 Correct 241 ms 22352 KB Output is correct
16 Correct 231 ms 22268 KB Output is correct
17 Correct 211 ms 22420 KB Output is correct
18 Correct 230 ms 22592 KB Output is correct
19 Correct 218 ms 22348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 1 ms 348 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 464 KB Output is correct
34 Execution timed out 1020 ms 163520 KB Time limit exceeded
35 Halted 0 ms 0 KB -