oj.uz

Submission #483766

# Submission time Handle Problem Language Result Execution time Memory
483766 2021-11-01T04:17:35 Z kawaii Peru (RMI20_peru) C++14
0 / 100
 1 ms 468 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma,bmi,bmi2")
 
#include <bits/stdc++.h>
using namespace std;
//define int long long
 
long long mod = 1e9 + 7, ans = 0;
int n, m, k, a[2500005], l2[2500005], mx[2500005][22], twt[2500005], b[2500005];
deque<pair<int, int> > dq;
 
 
int solve(int n, int k, int* a){
    twt[0] = 1;
    for(int i = 1; i <= n; i++){
        if(i >= 2) l2[i] = l2[i / 2] + 1;
        mx[i][0] = a[i];
        twt[i] = ((long long) twt[i - 1] * 23) % mod; 
    }
    for(int i = 0; i <= n; i++){
        for(int j = 1; i + (1 << (j - 1)) <= n; j++){
            mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
        }
    } 
    for(int i = 1; i <= n; i++){ 
        if(dq.size() == 0){
            dq.push_back(make_pair(a[i], i));  
            b[i] = a[i];
        }
        else{
            dq.push_front(make_pair(b[i - k], i - k)); 
            while(dq.size() > 0 && i - dq.front().second > k) dq.pop_front(); 
            long long p = 1e18;
            pair<int, int> t;
            while(dq.size() > 0){
                t = dq.front(); 
                int c = l2[i - t.second - 1], num = (((long long) t.first + max(mx[t.second + 1][c], mx[i - (1 << c) + 1][c]))) % mod;
                num = min((long long) num, ((long long) dq.back().first + a[i]) % mod); 
                if(num <= p){
                    p = num;
                    dq.pop_front();
                }
                else{
                    dq.push_back(make_pair(p, i));
                    b[i] = p;
                    break;
                }
                if(dq.size() == 0){
                    dq.push_back(make_pair(p, i));
                    b[i] = p;
                    break;
                }
            }  
        } 
        ans = (ans + (long long) b[i] * twt[n - i]) % mod;
        // cout << dq.size() << "\n";
        // for(auto i: dq) cout << i.first <<" "<< i.second <<"  "; cout << "\n";
        // cout << "\n";
    }
    return ans;
}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -