제출 #696721

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
696721		anhduc2701	Izbori (COCI22_izbori)	C++17	15 / 110	221 ms	44300 KiB

Main

/*
#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<=3;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;
}

컴파일 시 표준 에러 (stderr) 메시지

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++){
      |                  ~^~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 15 / 15
• Subtask 4: 0 / 70