# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
730500 |
2023-04-26T03:52:07 Z |
vjudge1 |
Izbori (COCI22_izbori) |
C++17 |
|
594 ms |
44256 KB |
/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define all(x) x.begin(), x.end()
#define len(x) ll(x.size())
#define eb emplace_back
#define PI 3.14159265359
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x) (1LL<<(x))
#define task "tnc"
typedef long long ll;
const ll INF=1e18;
const int maxn=1e6+5;
const int mod=1e9+7;
const int mo=998244353;
using pi=pair<ll,ll>;
using vi=vector<ll>;
using pii=pair<pair<ll,ll>,ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n,m;
int a[maxn];
vector<int>k[maxn];
stack<pair<int,int>>p;
int st[2*maxn];
int lazy[2*maxn];
int st1[2*maxn];
vector<int>vt;
int ans=0;
int getsum(int l,int r){
return (r-l+1)*(r+l)/2;
}
void push(int id,int l,int mid,int r){
st[id*2]+=lazy[id]*(mid-l+1);
st1[id*2]+=lazy[id]*getsum(1,mid-l+1);
st[id*2+1]+=lazy[id]*(r-mid);
st1[id*2+1]+=lazy[id]*getsum(1,r-mid);
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
lazy[id]=0;
}
void update(int id,int l,int r,int u,int v,int val){
if(r<u || v<l)return;
if(u<=l && r<=v){
st[id]+=val*(r-l+1);
st1[id]+=val*getsum(1,r-l+1);
lazy[id]+=val;
return;
}
int mid=(l+r)/2;
push(id,l,mid,r);
update(id*2,l,mid,u,v,val);
update(id*2+1,mid+1,r,u,v,val);
st[id]=st[id*2]+st[id*2+1];
st1[id]=st1[id*2]+st[id*2]*(r-mid)+st1[id*2+1];
}
int get(int id,int l,int r,int u,int v,int dis){
if(r<u || v<l)return 0;
if(u<=l && r<=v){
return st[id]*(dis);
}
int mid=(l+r)/2;
push(id,l,mid,r);
return get(id*2,l,mid,u,v,dis)+get(id*2+1,mid+1,r,u,v,dis);
}
int get1(int id,int l,int r,int u,int v){
if(r<u || v<l)return 0;
if(u<=l && r<=v ){
return st1[id]+st[id]*(v-r);
}
int mid=(l+r)/2;
push(id,l,mid,r);
return get1(id*2,l,mid,u,v)+get1(id*2+1,mid+1,r,u,v);
}
signed main()
{
cin.tie(0),cout.tie(0)->sync_with_stdio(0);
//freopen(task".inp" , "r" , stdin);
//freopen(task".out" , "w" , stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
vt.pb(a[i]);
}
sort(vt.begin(),vt.end());
vt.resize(distance(vt.begin(),unique(all(vt))));
for(int i=1;i<=n;i++){
a[i]=lower_bound(vt.begin(),vt.end(),a[i])-vt.begin()+1;
k[a[i]].pb(i);
}
for(int i=1;i<=n;i++){
while(p.size()){
pair<int,int>d=p.top();
p.pop();
update(1,1,2*n,d.fi,d.se,-1);
}
int ht=0;
for(int j=0;j<k[i].size();j++){
if(j==0){
p.push({n-k[i][j]+1,n});
update(1,1,2*n,n-k[i][j]+1,n,1);
ht-=k[i][j];
ht++;
}
ht++;
int dis;
if(j==(int)k[i].size()-1){
dis=n-k[i][j]+1;
}
else{
dis=k[i][j+1]-k[i][j];
}
ans+=get(1,1,2*n,1,ht-dis+n,dis);
ans+=get1(1,1,2*n,ht-dis+n+1,ht-1+n);
update(1,1,2*n,ht-dis+1+n,ht+n,1);
p.push(mp(ht-dis+1+n,ht+n));
ht-=dis;
ht++;
}
}
cout<<ans;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:109:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for(int j=0;j<k[i].size();j++){
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
16 ms |
23892 KB |
Output is correct |
3 |
Correct |
13 ms |
23848 KB |
Output is correct |
4 |
Correct |
13 ms |
23816 KB |
Output is correct |
5 |
Correct |
12 ms |
23812 KB |
Output is correct |
6 |
Correct |
12 ms |
23892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
16 ms |
23892 KB |
Output is correct |
3 |
Correct |
13 ms |
23848 KB |
Output is correct |
4 |
Correct |
13 ms |
23816 KB |
Output is correct |
5 |
Correct |
12 ms |
23812 KB |
Output is correct |
6 |
Correct |
12 ms |
23892 KB |
Output is correct |
7 |
Correct |
13 ms |
23852 KB |
Output is correct |
8 |
Correct |
12 ms |
23780 KB |
Output is correct |
9 |
Correct |
15 ms |
24036 KB |
Output is correct |
10 |
Correct |
14 ms |
23968 KB |
Output is correct |
11 |
Correct |
14 ms |
23952 KB |
Output is correct |
12 |
Correct |
14 ms |
24020 KB |
Output is correct |
13 |
Correct |
14 ms |
23972 KB |
Output is correct |
14 |
Correct |
14 ms |
24032 KB |
Output is correct |
15 |
Correct |
16 ms |
24028 KB |
Output is correct |
16 |
Correct |
16 ms |
24020 KB |
Output is correct |
17 |
Correct |
14 ms |
24020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
142 ms |
28944 KB |
Output is correct |
2 |
Correct |
166 ms |
29556 KB |
Output is correct |
3 |
Correct |
127 ms |
27204 KB |
Output is correct |
4 |
Correct |
182 ms |
30184 KB |
Output is correct |
5 |
Correct |
191 ms |
30488 KB |
Output is correct |
6 |
Correct |
203 ms |
30504 KB |
Output is correct |
7 |
Correct |
186 ms |
30520 KB |
Output is correct |
8 |
Correct |
185 ms |
30476 KB |
Output is correct |
9 |
Correct |
193 ms |
30588 KB |
Output is correct |
10 |
Correct |
196 ms |
30744 KB |
Output is correct |
11 |
Correct |
192 ms |
44256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
23764 KB |
Output is correct |
2 |
Correct |
16 ms |
23892 KB |
Output is correct |
3 |
Correct |
13 ms |
23848 KB |
Output is correct |
4 |
Correct |
13 ms |
23816 KB |
Output is correct |
5 |
Correct |
12 ms |
23812 KB |
Output is correct |
6 |
Correct |
12 ms |
23892 KB |
Output is correct |
7 |
Correct |
13 ms |
23852 KB |
Output is correct |
8 |
Correct |
12 ms |
23780 KB |
Output is correct |
9 |
Correct |
15 ms |
24036 KB |
Output is correct |
10 |
Correct |
14 ms |
23968 KB |
Output is correct |
11 |
Correct |
14 ms |
23952 KB |
Output is correct |
12 |
Correct |
14 ms |
24020 KB |
Output is correct |
13 |
Correct |
14 ms |
23972 KB |
Output is correct |
14 |
Correct |
14 ms |
24032 KB |
Output is correct |
15 |
Correct |
16 ms |
24028 KB |
Output is correct |
16 |
Correct |
16 ms |
24020 KB |
Output is correct |
17 |
Correct |
14 ms |
24020 KB |
Output is correct |
18 |
Correct |
142 ms |
28944 KB |
Output is correct |
19 |
Correct |
166 ms |
29556 KB |
Output is correct |
20 |
Correct |
127 ms |
27204 KB |
Output is correct |
21 |
Correct |
182 ms |
30184 KB |
Output is correct |
22 |
Correct |
191 ms |
30488 KB |
Output is correct |
23 |
Correct |
203 ms |
30504 KB |
Output is correct |
24 |
Correct |
186 ms |
30520 KB |
Output is correct |
25 |
Correct |
185 ms |
30476 KB |
Output is correct |
26 |
Correct |
193 ms |
30588 KB |
Output is correct |
27 |
Correct |
196 ms |
30744 KB |
Output is correct |
28 |
Correct |
192 ms |
44256 KB |
Output is correct |
29 |
Correct |
202 ms |
44224 KB |
Output is correct |
30 |
Correct |
101 ms |
28624 KB |
Output is correct |
31 |
Correct |
201 ms |
33220 KB |
Output is correct |
32 |
Correct |
594 ms |
43188 KB |
Output is correct |
33 |
Correct |
218 ms |
33432 KB |
Output is correct |
34 |
Correct |
262 ms |
33620 KB |
Output is correct |
35 |
Correct |
140 ms |
29320 KB |
Output is correct |
36 |
Correct |
93 ms |
28500 KB |
Output is correct |
37 |
Correct |
108 ms |
28708 KB |
Output is correct |
38 |
Correct |
239 ms |
37556 KB |
Output is correct |
39 |
Correct |
220 ms |
37184 KB |
Output is correct |
40 |
Correct |
218 ms |
37312 KB |
Output is correct |
41 |
Correct |
277 ms |
37392 KB |
Output is correct |
42 |
Correct |
220 ms |
37164 KB |
Output is correct |
43 |
Correct |
265 ms |
39744 KB |
Output is correct |
44 |
Correct |
255 ms |
39764 KB |
Output is correct |
45 |
Correct |
258 ms |
39648 KB |
Output is correct |
46 |
Correct |
263 ms |
39744 KB |
Output is correct |
47 |
Correct |
247 ms |
39672 KB |
Output is correct |
48 |
Correct |
345 ms |
41280 KB |
Output is correct |
49 |
Correct |
330 ms |
41344 KB |
Output is correct |
50 |
Correct |
308 ms |
41772 KB |
Output is correct |
51 |
Correct |
347 ms |
41816 KB |
Output is correct |
52 |
Correct |
322 ms |
41036 KB |
Output is correct |
53 |
Correct |
336 ms |
40860 KB |
Output is correct |
54 |
Correct |
315 ms |
41160 KB |
Output is correct |