#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ordered_set tree<pair<lng,lng>,null_type,less<pair<lng,lng>>,rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<double,null_type,less<double>,rb_tree_tag,tree_order_statistics_node_update>
#define rtr return 0
#define lng long long
#define double long double
#define endl "\n"
#define pb push_back
#define cmbntrcs fact[0]=1;for(int i=1;i<INF;i++){fact[i]=mul(i,fact[i-1]);}inv[INF-1]=mod_inv(fact[INF-1]);for(int i=INF-2;i>=0;i--){inv[i]=mul(inv[i+1],i+1);}
///#pragma GCC optimize(Ofast,unroll-all-loops)
const int INF=1e6+7,SZ=3e5+7,MSZ=1e5+3,MAXA=6e5+7;
int MOD=998244353;
int add(int x,int y){int z=x+y;if(z>=MOD){z-=MOD;}return z;}
int sub(int x,int y){int z=x-y;if(z<0){z+=MOD;}return z;}
int mul(int x,int y){return(x*1ll*y)%MOD;}
int pwr(int a,lng b)
{
int rs=1;
while(b>0){if(b&1){rs=mul(rs,a);}a=mul(a,a);b>>=1;}
return rs;
}
int mod_inv(int a){return pwr(a,MOD-2);}
int fact[INF],inv[INF];
int nCr(int n,int r){if(r>n||r<0||n<0){return 0;}return mul(fact[n],mul(inv[r],inv[n-r]));}
int nPr(int n,int r){if(r>n||r<0||n<0){return 0;}return mul(fact[n],inv[n-r]);}
int nPrvc(vector<int>r)
{
int den=1,n=0;
for(int i=0;i<r.size();i++){den=mul(den,inv[r[i]]);n+=r[i];}
return mul(fact[n],den);
}
int sb(int s,int b){if(s<0||b<0){return 0;}return nCr(s+b-1,s);}
int prfx(int i,int j){if(i<0||j<0){return 0;}return nCr(i+j,i);}
int nCrL(int x,int y)
{
int rt=1;for(int i=x;i>x-y;i--){rt=mul(rt,i);}
int dn=1;for(int i=1;i<=y;i++){dn=mul(dn,i);}
return mul(rt,mod_inv(dn));
}
lng lcm(lng x,lng y){return((x/__gcd(x,y))*y);}
lng trig(lng x){return x*(x+1)/2;}
lng pent(lng x){return(x*((3*x)-1))/2;}
lng sigma(lng x,lng y){return trig(y)-trig(x-1);}
pair<double,double>quad(double a,double b,double c)
{
double disc=(b*b)-(4*a*c);
if(disc<0){return{-1e16,-1e16};}
return{(sqrt(disc)-b)/(2*a),-(sqrt(disc)+b)/(2*a)};
}
double sigma_rev(double x){return quad(1,1,-2*x).first;}
lng cldv(lng a,lng b){return(a+b-1)/b;}
lng fp(lng a,lng b)
{
lng rs=1;
while(b>0){if(b&1){rs*=a;}a*=a;b>>=1;}
return rs;
}
struct mtrx
{
lng nx,mx;vector<vector<lng>>bd;
void bld(vector<vector<lng>>obd){nx=obd.size(),mx=obd[0].size();bd=obd;}
void outm(){for(lng i=0;i<nx;i++){for(lng j=0;j<mx;j++){cout << bd[i][j] << ' ';}cout << endl;}}
};
mtrx idnt(lng n)
{
vector<vector<lng>>v;v.resize(n);
for(lng i=0;i<n;i++){v[i].assign(n,0);v[i][i]=1;}
return{n,n,v};
}
mtrx mulm(mtrx a,mtrx b)
{
if(a.mx!=b.nx){return{1,1,{{0}}};}
vector<vector<lng>>v;v.resize(a.nx);
for(lng i=0;i<a.nx;i++)
{
v[i].resize(b.mx);
for(lng j=0;j<b.mx;j++)
{
lng s=0;
for(lng x=0;x<a.mx;x++)
{
s+=a.bd[i][x]*b.bd[x][j];
s%=MOD;
}
v[i][j]=s;
}
}
mtrx ret;ret.bld(v);
return ret;
}
mtrx fpm(mtrx a,lng b)
{
if(b==0){return idnt(a.nx);}
mtrx ret=fpm(a,b/2);ret=mulm(ret,ret);
if(b%2){ret=mulm(ret,a);}
return ret;
}
lng rndm(lng a,lng b){return a+rng()%((b+1)-a);}
struct dsu
{
vector<lng>p,sz;
void init(lng n)
{
p.resize(n+1);sz.assign(n+1,1);
for(lng i=0;i<=n;i++){p[i]=i;}
return;
}
lng get(lng a)
{
if(p[a]==a){return a;}
return p[a]=get(p[a]);
}
void unn(lng x,lng y)
{
if(cnct(x,y)){return;}
x=get(x);y=get(y);
if(sz[x]>sz[y]){swap(x,y);}
p[x]=y;sz[y]+=sz[x];return;
}
bool cnct(lng x,lng y){return get(x)==get(y);}
lng siz(lng a){return sz[get(a)];}
};
lng n,c=0,vs[INF]{},a[INF];set<lng>st[INF];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
for(lng i=0;i<n;i++){cin >> a[i];st[a[i]].insert(i);}
for(lng i=0;i<n;i++)
{
if(vs[i]){continue;}
c++;int x=a[i],ps=i;
while(true)
{
vs[ps]=1;st[x].erase(st[x].find(ps));
x--;if(st[x].empty()){break;}
if(st[x].upper_bound(ps)==st[x].end()){break;}
ps=*st[x].upper_bound(ps);
}
}
cout << c;
return 0;
}
Compilation message
baloni.cpp: In function 'int nPrvc(std::vector<int>)':
baloni.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for(int i=0;i<r.size();i++){den=mul(den,inv[r[i]]);n+=r[i];}
| ~^~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
47316 KB |
Output is correct |
| 2 |
Correct |
24 ms |
47388 KB |
Output is correct |
| 3 |
Correct |
24 ms |
47564 KB |
Output is correct |
| 4 |
Correct |
23 ms |
47572 KB |
Output is correct |
| 5 |
Correct |
893 ms |
100308 KB |
Output is correct |
| 6 |
Correct |
981 ms |
106444 KB |
Output is correct |
| 7 |
Correct |
766 ms |
95820 KB |
Output is correct |
| 8 |
Correct |
753 ms |
95428 KB |
Output is correct |
| 9 |
Correct |
870 ms |
98284 KB |
Output is correct |
| 10 |
Correct |
927 ms |
100060 KB |
Output is correct |
