제출 #1130940

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130940		8pete8	Diversity (CEOI21_diversity)	C++20	64 / 100	7086 ms	68520 KiB

diversity

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define int long long
using namespace std;
const int mod=1e9+7,mxn=3e5+5,inf=1e18,minf=-1e18,lg=30,base=191;
//#undef int
int n,q;
int val[mxn+10];
struct seg{
    int cnt[4*mxn+10],sum[4*mxn+10][2],sumpref[4*mxn+10][2],sumsquare[4*mxn+10][2];
    int vx[4*mxn+10][2];
    void merge(int l,int r,int pos){
        cnt[pos]=cnt[l]+cnt[r];
        for(int j=0;j<2;j++){
            int x=cnt[l]%2,cr=cnt[r]/2;
            if((x^j)&&cnt[r]%2)cr++;
            sum[pos][j]=sum[l][j]+sum[r][j^x];
            sumpref[pos][j]=sumpref[l][j]+(sum[l][j]*cr)+sumpref[r][j^x];
            sumsquare[pos][j]=sumsquare[l][j]+sumsquare[r][j^x]+(2*(sum[l][j]*sumpref[r][j^x]))
            +cr*(sum[l][j]*sum[l][j]);
            vx[pos][j]=vx[l][j]+vx[r][j^x]+(sum[r][j^x]*sum[l][j]);
        }
    }
    void update(int pos,int l,int r,int qpos,int V,int C){
        if(l==r){
            cnt[pos]=C;
            sum[pos][0]=sumpref[pos][0]=sumsquare[pos][0]=0;
            sum[pos][1]=sumpref[pos][1]=V;
            sumsquare[pos][1]=vx[pos][1]=V*V;
            return;
        }
        int mid=l+(r-l)/2;
        if(qpos<=mid)update(pos*2,l,mid,qpos,V,C);
        else update(pos*2+1,mid+1,r,qpos,V,C);
        merge(pos*2,pos*2+1,pos);
    }
}t;
int root=1000,cursz[mxn+10],ans[mxn+10],curans=0,ord[mxn+10];
bool cmp(pair<pii,int> a,pair<pii,int> b){
    if((a.f.f/root)==(b.f.f/root))return a.f.s<b.f.s;
    return (a.f.f/root)<(b.f.f/root);
}
int get(int x){return (x*(x+1))/2;}
void add(int x){
    curans+=(cursz[x]*cursz[x]);
    curans-=get(cursz[x]);
    int pos=0;
    int l=1,r=n;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(ord[mid]<=cursz[x])l=mid+1,pos=max(pos,mid);
        else r=mid-1;
    }
    ord[pos]++;
    t.update(1,1,n,pos,ord[pos],1);
    cursz[x]++;
    curans+=get(cursz[x]);
    curans-=(cursz[x]*cursz[x]);
}
void del(int x){
    curans+=(cursz[x]*cursz[x]);
    curans-=get(cursz[x]);
    int pos=n;
    int l=1,r=n;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(ord[mid]>=cursz[x])r=mid-1,pos=min(pos,mid);
        else l=mid+1;
    }
    ord[pos]--;
    t.update(1,1,n,pos,ord[pos],(!!ord[pos]));
    cursz[x]--;
    curans+=get(cursz[x]);
    curans-=(cursz[x]*cursz[x]);
}
int getra(int l,int r){
    int ra=0;
    for(int j=0;j<2;j++){
        ra+=(t.sumpref[1][j]*(r-l+1));
        ra-=t.sumsquare[1][j];
        ra+=t.vx[1][j];
        ra-=t.sum[1][j]*(r-l+1);
    }
    return ra;
}
/*
mo's algo would this pass??
*/
int32_t main(){
    fastio
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>val[i];
    vector<pair<pii,int>>qry(q);
    for(int i=0;i<q;i++)cin>>qry[i].f.f>>qry[i].f.s,qry[i].s=i;
    sort(all(qry),cmp);
    int l=-1,r=-1;
    int cnt=0;
    /*
    (n+q)sqrt(n)log(n)
    sz
    (n(n/sz)+qsz)log(n)
    (9e10/sz+5e4sz)19
    */
    for(int i=0;i<q;i++){
        if(i&&(qry[i].f.f/root)!=(qry[i-1].f.f/root))cnt++;
        if(l==-1){
            for(int c=qry[i].f.f;c<=qry[i].f.s;c++)add(val[c]);
            l=qry[i].f.f,r=qry[i].f.s;
            ans[qry[i].s]=(r-l+1)*(r-l+1)+curans+getra(l,r);
            continue;
        }
        while(r<qry[i].f.s){
            add(val[r+1]);
            r++;
        }
        while(r>qry[i].f.s){
            del(val[r]);
            r--;
        }
        while(l>qry[i].f.f){
            add(val[l-1]);
            l--;
        }
        while(l<qry[i].f.f){
            del(val[l]);
            l++;
        }
        ans[qry[i].s]=(r-l+1)*(r-l+1)+curans+getra(l,r);
    }
    if(cnt>300)assert(0);
    for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
}
/*
3 1
1 2 3
1 3

4 2
1 1 1 1
1 2
2 4

5 3
1 2 1 3 2
2 5
1 3
3 4

5 1
1 5 1 3 5
2 5
*/

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

diversity.cpp:32:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   32 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
diversity.cpp:42:35: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   42 |     void merge(int l,int r,int pos){
      |                                   ^
diversity.cpp:54:57: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   54 |     void update(int pos,int l,int r,int qpos,int V,int C){
      |                                                         ^
diversity.cpp:69:41: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   69 | bool cmp(pair<pii,int> a,pair<pii,int> b){
      |                                         ^
diversity.cpp:73:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   73 | int get(int x){return (x*(x+1))/2;}
      |              ^
diversity.cpp:74:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   74 | void add(int x){
      |               ^
diversity.cpp:90:15: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   90 | void del(int x){
      |               ^
diversity.cpp:106:22: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  106 | int getra(int l,int r){
      |                      ^
diversity.cpp:119:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
  119 | int32_t main(){
      |              ^

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 0 / 36