Submission #831771

#	Time	Username	Problem	Language	Result	Execution time	Memory
831771		nnin	Pilot (NOI19_pilot)	C++14	100 / 100	439 ms	53092 KiB

pilot

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
using namespace std;

int n, q;
ll ans[1000002];
pii y[1000002], h[1000002];

ll ctFlights(int mount) {
    return (ll)mount*(mount+1)/2;
}

int dsu[1000002], sz[1000002];
bool over[1000002];
int par(int x) {
    if(dsu[x]==0) return x;
    else return dsu[x] = par(dsu[x]);
}

ll curct;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        cin>>h[i].f;
        h[i].s = i;
    }
    sort(h+1, h+n+1);
    for(int i=1;i<=q;i++) {
        cin>>y[i].f;
        y[i].s = i;
    }
    sort(y+1, y+q+1);
    int hi = 1;
    for(int yi=1;yi<=q;yi++) {
        while(hi<=n && h[hi].f<=y[yi].f) {
            over[h[hi].s] = 1;
            sz[h[hi].s] = 1;
            if(h[hi].s+1<=n && over[h[hi].s+1]) {
                int p = par(h[hi].s+1);
                curct -= ctFlights(sz[p]);
                dsu[p] = h[hi].s;
                sz[h[hi].s] += sz[p];
            }
            if(h[hi].s-1>=1 && over[h[hi].s-1]) {
                int p = par(h[hi].s-1);
                curct -= ctFlights(sz[p]);
                dsu[h[hi].s] = p;
                sz[p] += sz[h[hi].s];
            }
            curct += ctFlights(sz[par(h[hi].s)]);
            hi++;
        }
        ans[y[yi].s] = curct;
    }
    for(int i=1;i<=q;i++) {
        cout<<ans[i]<<'\n';
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11