Submission #760789

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
760789	2023-06-18 12:57:12	bachhoangxuan	Fountain (eJOI20_fountain)	C++17	100 / 100	301 ms	10264 KiB

fountain

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define maxn 100005
const int inf=1e18;
const int bl=320;
int n,q,a[maxn],x[maxn],nxt[maxn],sum[maxn],sxt[maxn];
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i=1;i<=n;i++)cin >> a[i] >> x[i];
    a[n+1]=x[n+1]=inf;
    vector<int> Max;Max.push_back(n+1);
    for(int i=n;i>=1;i--){
        while(a[i]>=a[Max.back()]) Max.pop_back();
        nxt[i]=Max.back();Max.push_back(i);
    }
    for(int i=1;i<=n;i++){
        int u=i;
        for(int j=0;j<bl;j++){
            sum[i]+=x[u];
            if(u==n+1) break;
            else u=nxt[u];
        }
        sxt[i]=u;
    }
    for(int i=1;i<=q;i++){
        int r,v;cin >> r >> v;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40