# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
888417 |
2023-12-17T10:31:08 Z |
imarn |
Pilot (NOI19_pilot) |
C++14 |
|
29 ms |
15316 KB |
#include<bits/stdc++.h>
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define f first
#define s second
#define vi vector<int>
#define vpii vector<pii>
#define ll long long
using namespace std;
const int N=1e6+5;
int pr[N],a[N];
pii qr[N];
int sz[N];
int ac[N];
bool vis[N]{0};
vector<pii>v;
int get(int r){
return pr[r]==r?r:pr[r]=get(pr[r]);
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int n,q;cin>>n>>q;iota(pr,pr+n+1,0);
for(int i=1;i<=n;i++)cin>>a[i],sz[i]=1;
for(int i=1;i<=q;i++)cin>>qr[i].f,qr[i].s=i;
int ans=0;sort(qr+1,qr+q+1);
int sn=0;
for(int i=1;i<=n;i++){
if(sn==0&&a[i]<=qr[1].f)sn++,vis[i]=1,sz[i]=sn;
else if(sn>0&&a[i]<=qr[1].f)pr[i-1]=i,sn++,vis[i]=1,sz[i]=sn;
else if(a[i]>qr[1].f)v.pb({a[i],i}),ans+=sn*(sn+1)/2,sn=0;
}ans+=sn*(sn+1)/2;
sort(v.begin(),v.end());
ac[qr[1].s]=ans;int idx=0;
for(int i=2;i<=q;i++){
while(idx<v.size()&&qr[i].f>=v[idx].f){
int j = v[idx].s;
ans+=1;vis[j]=1;
if(vis[j-1]){
pr[j-1]=j;ans-=sz[j]*(sz[j]+1)/2;
ans-=sz[j-1]*(sz[j-1]+1)/2;sz[j]+=sz[j-1];
ans+=sz[j]*(sz[j]+1)/2;
}
if(vis[j+1]){
int u=get(j+1);
pr[j]=pr[u];ans-=sz[j]*(sz[j]+1)/2;
ans-=sz[u]*(sz[u]+1)/2;sz[u]+=sz[j];
ans+=sz[u]*(sz[u]+1)/2;
}idx++;
}ac[qr[i].s]=ans;
}for(int i=1;i<=q;i++)cout<<ac[i]<<"\n";
}
Compilation message
pilot.cpp: In function 'int main()':
pilot.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | while(idx<v.size()&&qr[i].f>=v[idx].f){
| ~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10704 KB |
Output is correct |
2 |
Correct |
1 ms |
10584 KB |
Output is correct |
3 |
Correct |
1 ms |
10588 KB |
Output is correct |
4 |
Correct |
1 ms |
10724 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
1 ms |
10588 KB |
Output is correct |
7 |
Correct |
1 ms |
10584 KB |
Output is correct |
8 |
Correct |
1 ms |
10584 KB |
Output is correct |
9 |
Correct |
1 ms |
10588 KB |
Output is correct |
10 |
Correct |
1 ms |
10588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10704 KB |
Output is correct |
2 |
Correct |
1 ms |
10584 KB |
Output is correct |
3 |
Correct |
1 ms |
10588 KB |
Output is correct |
4 |
Correct |
1 ms |
10724 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
1 ms |
10588 KB |
Output is correct |
7 |
Correct |
1 ms |
10584 KB |
Output is correct |
8 |
Correct |
1 ms |
10584 KB |
Output is correct |
9 |
Correct |
1 ms |
10588 KB |
Output is correct |
10 |
Correct |
1 ms |
10588 KB |
Output is correct |
11 |
Correct |
1 ms |
10588 KB |
Output is correct |
12 |
Correct |
1 ms |
10588 KB |
Output is correct |
13 |
Correct |
1 ms |
10588 KB |
Output is correct |
14 |
Correct |
1 ms |
10584 KB |
Output is correct |
15 |
Correct |
1 ms |
10584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10704 KB |
Output is correct |
2 |
Correct |
1 ms |
10584 KB |
Output is correct |
3 |
Correct |
1 ms |
10588 KB |
Output is correct |
4 |
Correct |
1 ms |
10724 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
1 ms |
10588 KB |
Output is correct |
7 |
Correct |
1 ms |
10584 KB |
Output is correct |
8 |
Correct |
1 ms |
10584 KB |
Output is correct |
9 |
Correct |
1 ms |
10588 KB |
Output is correct |
10 |
Correct |
1 ms |
10588 KB |
Output is correct |
11 |
Correct |
1 ms |
10588 KB |
Output is correct |
12 |
Correct |
1 ms |
10588 KB |
Output is correct |
13 |
Correct |
1 ms |
10588 KB |
Output is correct |
14 |
Correct |
1 ms |
10584 KB |
Output is correct |
15 |
Correct |
1 ms |
10584 KB |
Output is correct |
16 |
Correct |
2 ms |
10588 KB |
Output is correct |
17 |
Correct |
1 ms |
10588 KB |
Output is correct |
18 |
Correct |
1 ms |
10588 KB |
Output is correct |
19 |
Correct |
1 ms |
10588 KB |
Output is correct |
20 |
Correct |
2 ms |
10840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10704 KB |
Output is correct |
2 |
Correct |
1 ms |
10584 KB |
Output is correct |
3 |
Correct |
1 ms |
10588 KB |
Output is correct |
4 |
Correct |
1 ms |
10724 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
1 ms |
10588 KB |
Output is correct |
7 |
Correct |
1 ms |
10584 KB |
Output is correct |
8 |
Correct |
1 ms |
10584 KB |
Output is correct |
9 |
Correct |
1 ms |
10588 KB |
Output is correct |
10 |
Correct |
1 ms |
10588 KB |
Output is correct |
11 |
Correct |
1 ms |
10588 KB |
Output is correct |
12 |
Correct |
1 ms |
10588 KB |
Output is correct |
13 |
Correct |
1 ms |
10588 KB |
Output is correct |
14 |
Correct |
1 ms |
10584 KB |
Output is correct |
15 |
Correct |
1 ms |
10584 KB |
Output is correct |
16 |
Correct |
2 ms |
10588 KB |
Output is correct |
17 |
Correct |
1 ms |
10588 KB |
Output is correct |
18 |
Correct |
1 ms |
10588 KB |
Output is correct |
19 |
Correct |
1 ms |
10588 KB |
Output is correct |
20 |
Correct |
2 ms |
10840 KB |
Output is correct |
21 |
Correct |
2 ms |
10588 KB |
Output is correct |
22 |
Correct |
2 ms |
10736 KB |
Output is correct |
23 |
Correct |
2 ms |
10588 KB |
Output is correct |
24 |
Correct |
2 ms |
10588 KB |
Output is correct |
25 |
Correct |
2 ms |
10588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
13280 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
28 ms |
15316 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
29 ms |
15296 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10704 KB |
Output is correct |
2 |
Correct |
1 ms |
10584 KB |
Output is correct |
3 |
Correct |
1 ms |
10588 KB |
Output is correct |
4 |
Correct |
1 ms |
10724 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
1 ms |
10588 KB |
Output is correct |
7 |
Correct |
1 ms |
10584 KB |
Output is correct |
8 |
Correct |
1 ms |
10584 KB |
Output is correct |
9 |
Correct |
1 ms |
10588 KB |
Output is correct |
10 |
Correct |
1 ms |
10588 KB |
Output is correct |
11 |
Incorrect |
9 ms |
13280 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10704 KB |
Output is correct |
2 |
Correct |
1 ms |
10584 KB |
Output is correct |
3 |
Correct |
1 ms |
10588 KB |
Output is correct |
4 |
Correct |
1 ms |
10724 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
1 ms |
10588 KB |
Output is correct |
7 |
Correct |
1 ms |
10584 KB |
Output is correct |
8 |
Correct |
1 ms |
10584 KB |
Output is correct |
9 |
Correct |
1 ms |
10588 KB |
Output is correct |
10 |
Correct |
1 ms |
10588 KB |
Output is correct |
11 |
Correct |
1 ms |
10588 KB |
Output is correct |
12 |
Correct |
1 ms |
10588 KB |
Output is correct |
13 |
Correct |
1 ms |
10588 KB |
Output is correct |
14 |
Correct |
1 ms |
10584 KB |
Output is correct |
15 |
Correct |
1 ms |
10584 KB |
Output is correct |
16 |
Correct |
2 ms |
10588 KB |
Output is correct |
17 |
Correct |
1 ms |
10588 KB |
Output is correct |
18 |
Correct |
1 ms |
10588 KB |
Output is correct |
19 |
Correct |
1 ms |
10588 KB |
Output is correct |
20 |
Correct |
2 ms |
10840 KB |
Output is correct |
21 |
Correct |
2 ms |
10588 KB |
Output is correct |
22 |
Correct |
2 ms |
10736 KB |
Output is correct |
23 |
Correct |
2 ms |
10588 KB |
Output is correct |
24 |
Correct |
2 ms |
10588 KB |
Output is correct |
25 |
Correct |
2 ms |
10588 KB |
Output is correct |
26 |
Incorrect |
9 ms |
13280 KB |
Output isn't correct |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
10704 KB |
Output is correct |
2 |
Correct |
1 ms |
10584 KB |
Output is correct |
3 |
Correct |
1 ms |
10588 KB |
Output is correct |
4 |
Correct |
1 ms |
10724 KB |
Output is correct |
5 |
Correct |
2 ms |
10588 KB |
Output is correct |
6 |
Correct |
1 ms |
10588 KB |
Output is correct |
7 |
Correct |
1 ms |
10584 KB |
Output is correct |
8 |
Correct |
1 ms |
10584 KB |
Output is correct |
9 |
Correct |
1 ms |
10588 KB |
Output is correct |
10 |
Correct |
1 ms |
10588 KB |
Output is correct |
11 |
Correct |
1 ms |
10588 KB |
Output is correct |
12 |
Correct |
1 ms |
10588 KB |
Output is correct |
13 |
Correct |
1 ms |
10588 KB |
Output is correct |
14 |
Correct |
1 ms |
10584 KB |
Output is correct |
15 |
Correct |
1 ms |
10584 KB |
Output is correct |
16 |
Correct |
2 ms |
10588 KB |
Output is correct |
17 |
Correct |
1 ms |
10588 KB |
Output is correct |
18 |
Correct |
1 ms |
10588 KB |
Output is correct |
19 |
Correct |
1 ms |
10588 KB |
Output is correct |
20 |
Correct |
2 ms |
10840 KB |
Output is correct |
21 |
Correct |
2 ms |
10588 KB |
Output is correct |
22 |
Correct |
2 ms |
10736 KB |
Output is correct |
23 |
Correct |
2 ms |
10588 KB |
Output is correct |
24 |
Correct |
2 ms |
10588 KB |
Output is correct |
25 |
Correct |
2 ms |
10588 KB |
Output is correct |
26 |
Incorrect |
9 ms |
13280 KB |
Output isn't correct |
27 |
Halted |
0 ms |
0 KB |
- |