제출 #1202359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1202359		zeta7532	September (APIO24_september)	C++20	100 / 100	326 ms	22564 KiB

september

#include "september.h"
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
using ll = int;
const ll mod = 998244353;
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define faster ios::sync_with_stdio(false);cin.tie(nullptr)

#include <vector>

template <typename T>
struct RMQ{
    const T INF=0;
    ll N;
    vector<T> dat,lazy;
    RMQ(ll N_):N(),dat(N_*4,INF),lazy(N_*4,-1){
        ll x=1;
        while(N_>x) x*=2;
        N=x;
    }
    void eval(ll k,ll l,ll r){
        if(lazy[k]==-1) return;
        if(k<N-1){
            lazy[k*2+1]=lazy[k];
            lazy[k*2+2]=lazy[k];
        }
        dat[k]=lazy[k]*(r-l);
        lazy[k]=-1;
    }
    void update(ll a,ll b,T x,ll k,ll l,ll r){
        eval(k,l,r);
        if(a<=l&&r<=b){
            lazy[k]=x;
            eval(k,l,r);
        }else if(a<r&&l<b){
            update(a,b,x,k*2+1,l,(l+r)/2);
            update(a,b,x,k*2+2,(l+r)/2,r);
            dat[k]=dat[k*2+1]+dat[k*2+2];
        }
    }
    void update(ll a,ll b,T x){update(a,b,x,0,0,N);}
    T query_sub(ll a,ll b,ll k,ll l,ll r){
        eval(k,l,r);
        if(r<=a||b<=l){
            return INF;
        }else if(a<=l&&r<=b){
            return dat[k];
        }else{
            T vl=query_sub(a,b,k*2+1,l,(l+r)/2);
            T vr=query_sub(a,b,k*2+2,(l+r)/2,r);
            return vl+vr;
        }
    }
    T query(ll a,ll b){return query_sub(a,b,0,0,N);}
};

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	vector<ll> E(N);
	rep(i,N) E[i]=i;
	vector<vector<ll>> B(M,vector<ll>(N,-1));
	rep(loop,M){
		S[loop].push_back(0);
		vector<ll> A=S[loop];
		rep(i,N) B[loop][A[i]]=i;
		vector<ll> C(N);
		vector<vector<ll>> G(N);
		rep(i,N){
			if(i==0) continue;	
			G[F[i]].push_back(i);
		}
		function<void(ll)> dfs=[&](ll v){
			C[B[loop][v]]=B[loop][v];
			for(ll nv:G[v]){
				dfs(nv);
				C[B[loop][v]]=max(C[B[loop][v]],C[B[loop][nv]]);
			}
		};
		dfs(0);
		rep(i,N) E[i]=max(E[i],C[i]);
	}
	ll now=0;
	vector<long long> cnt(M,0);
	vector<long long> pow(N,1);
	rep(i,N-1){
		pow[i+1]=pow[i]*2;
		if(pow[i+1]>=mod) pow[i+1]-=mod;
	}
	rep(i,N){
		rep(j,M){
			cnt[j]+=pow[S[j][i]];
			cnt[j]%=mod;
		}
		bool ok=true;
		rep(j,M-1){
			if(cnt[j]!=cnt[j+1]) ok=false;
		}
		if(ok){
			E[now]=max(E[now],i);
			now=i+1;
		}
	}
	RMQ<ll> seg(N);
	rep(i,N){
		ll D=seg.query(i,i+1);
		if(D==0){
			if(i==0) D=1; 
			if(i>=1) D=seg.query(i-1,i)+1;
		}
		seg.update(i,E[i]+1,D);
	}
	return seg.query(N-1,N)-1;
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16