Submission #526307

#TimeUsernameProblemLanguageResultExecution timeMemory
526307sudheerays123Pilot (NOI19_pilot)C++17
100 / 100
521 ms67784 KiB
#include <bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define ll long long int #define tc ll test;cin >> test;while(test--) #define vi vector<ll> #define pll pair<ll,ll> #define pb push_back #define mp make_pair #define INF 1e18 #define MOD 1000000007 #define ff first #define ss second #define in >> #define out << #define space << " " << #define spacef << " " #define fo(i,a,b) for(ll i = a; i <= b; i++) #define rfo(i,a,b) for(ll i = a; i >= b; i--) #define nextline out "\n" #define print(x) for(auto i : x ) cout out i spacef #define mmax(x,i) x = max(x,i) #define mmin(x,i) x = min(x,i) #define N 1000005 vi parent(N); vi ssize(N); void make_set(ll n){ fo(i,1,n){ parent[i] = i; ssize[i] = 1; } } ll find(ll x){ if(x == parent[x]) return x; return parent[x] = find(parent[x]); } ll cnt = 0; void add_edge(ll a , ll b){ a = find(a); b = find(b); if(a == b) return; parent[b] = a; cnt += ssize[a]*ssize[b]; ssize[a] += ssize[b]; } int main() { fast; ll n,q; cin in n in q; vi h(n+5); vector<pll> height(n+5); fo(i,1,n){ cin in h[i]; height[i].first = h[i]; height[i].second = i; } sort(height.begin()+1,height.begin()+n+1); make_set(n); vi ans(N,-INF); ans[0] = 0; fo(i,1,n){ cnt++; ll hi = height[i].first; ll index = height[i].second; if(index > 1 && h[index-1] <= hi){ add_edge(index,index-1); } if(index < n && h[index+1] <= hi){ add_edge(index,index+1); } ans[hi] = cnt; } fo(i,1,N) if(ans[i] == -INF) ans[i] = ans[i-1]; while(q--){ ll x; cin in x; cout out ans[x] nextline; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...