Submission #572408

#	Time	Username	Problem	Language	Result	Execution time	Memory
572408		MODDI	Pilot (NOI19_pilot)	C++14	100 / 100	723 ms	89792 KiB

pilot

#include <bits/stdc++.h>
#define int ll
using namespace std;
 
#define ll long long
#define f first
#define s second
#define pii pair<int, int>
 
#define MX(a,b) a=max(a,b)
#define MN(a,b) a=min(a,b)
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
 
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define pb push_back
 
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
 
const int maxn = 1e6+5;
 
int par[maxn];
int sz[maxn];
bool on[maxn];
 
ll re = 0;
int find(int x) {return x == par[x]?x:par[x] = find(par[x]);}
void mrg(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    re -= sz[a] * (sz[a]+1) / 2;
    re -= sz[b] * (sz[b]+1) / 2;
    sz[a] += sz[b];
    re += sz[a] * (sz[a]+1) / 2;
    par[b] = a;
}
vector<int> yay[maxn];
ll ans[maxn];
signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);
 
    int n,q; cin>>n>>q;
    REP(i,n) par[i] = i, sz[i] = 1;
    REP(i,n) {
        int a; cin>>a; yay[a].pb(i);
    }
    REP1(i, 1000000) {
        for (int x : yay[i]) {
            ++re;
            on[x] = 1;
            if (x && on[x-1]) mrg(x, x-1);
            if (x!=n-1 && on[x+1]) mrg(x, x+1);
        }
        ans[i] = re;
    }
 
    REP(i,q) {
        int x; cin>>x;
        cout<<ans[x]<<endl;
    }
}

• 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