oj.uz

Submission #633217

# Submission time Handle Problem Language Result Execution time Memory
633217 2022-08-21T23:37:59 Z cmll02 Rarest Insects (IOI22_insects) C++17
100 / 100
 74 ms 460 KB 
// 从未在意的名字永远不会被提起 - 雪葉/鹤见江野
#ifndef LOCAL
#include "insects.h"
#endif
/*
+
++
+++
++++
+++++
++++++
+++++++
++++++++
+++++++++
++++++++++
+++++++++++
++++++++++++
+++++++++++++
++++++++++++++
+++++++++++++++
++++++++++++++++
+++++++++++++++++
++++++++++++++++++
+ +++++++++++++++++
+  ++++++++++++++ ++
+   +++++++++++++  ++
+    ++++++++++++   ++
+     +++++++++++    ++
+      ++++++++++     ++
+       +++++++++      ++
+        ++++++++       ++
+         +++++++++++++++++
+          +++++++++++++++++
+           ++++++++++++++
+            +++++++++++
+             ++++++++
+              +++++
+               ++
+               +
+               +
+              ++
+             +++
+            ++++
+           +++++
+           +++++
+           +++++
+           +++++
+     +     +++++
+    +++    +++++
+   ++ ++   +++++
+  ++   ++  +++++
+ ++  +  ++ +++++
+++  +++  +++++++
++  ++ ++  ++++++
 
 
 ++++++++      +++++++++++     +++      +++        ++++++++        ++++++++
+++++++++     +++++++++++++    +++      +++       +++    +++      +++    +++
+++          +++   +++   +++   +++      +++      +++   ++++++    +++      +++
+++          +++   +++   +++   +++      +++      +++ +++  +++           +++
+++          +++   +++   +++   +++ ++   +++ ++   ++++++   +++         +++
+++++++++    +++   +++   +++   +++ ++   +++ ++    +++    +++        +++    ++
 ++++++++    +++   +++   +++   +++++    +++++      ++++++++       +++++++++++
*/
#ifndef ONLINE_JUDGE
#define DEBUG
#endif
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <assert.h>
#include <math.h>
#include <set>
#define nln puts("")
#define od(x) printf("%d",x)
#define odb(x) printf("%d ",x)
#define odl(x) printf("%d\n",x)
#define odp(x,y) printf("%d %d\n",x,y)
#define ol(x) puts("")
#define old(x) printf("%lld",x)
#define oldb(x) printf("%lld ",x)
#define oldl(x) printf("%lld\n",x)
#define oldp(x,y) printf("%lld %lld\n",x,y)
#define rg(x) for(int i=1;i<=(x);i++){
#define rg_(i,x) for(int i=1;i<=(x);i++){
#define fe(u) for(int i=h[u];i;i=e[i].nxt){int v=e[i].v;
#define gr }
#define rrg(x) for(int i=0;i<(x);i++){
#define rdln(a) a[i]=read();
#define rdln0(a,x) rrg(x) rdln(a) gr
#define rdln1(a,x) rg(x) rdln(a) gr
template<typename T>
void print(T x){}
template<>
void print<int>(int x){od(x);}
template<>
void print<const int>(const int x){od(x);}
template<>
void print<long long>(long long x){old(x);}
template<>
void print<const long long>(const long long x){old(x);}
template<>
void print<char>(char x){putchar(x);}
template<>
void print<const char>(const char x){putchar(x);}
template<>
void print<double>(double x){printf("%.12lf",x);}
template<typename T,typename... qwq>
void print(T x,qwq ...args)
{
	print(x);
	print(args...);
}
#ifdef DEBUG
template<typename T>
void debug(T x){}
template<>
void debug<int>(int x){od(x);}
template<>
void debug<const int>(const int x){od(x);}
template<>
void debug<long long>(long long x){old(x);}
template<>
void debug<const long long>(const long long x){old(x);}
template<>
void debug<char>(char x){putchar(x);}
template<>
void debug<const char>(const char x){putchar(x);}
template<>
void debug<double>(double x){printf("%.12lf",x);}
template<typename T,typename... qwq>
void debug(T x,qwq ...args)
{
	debug(x);
	debug(args...);
}
#define dflush fflush
#else
#define dflush(...) 0
template<typename T,typename... qwq>
void debug(T x,qwq ...args)
{
	
}
#endif

#define int long long
const int mod=1e9+2022;
#ifdef int 
#define inf 0x3f3f3f3f3f3f3f3fll
#else 
#define inf 0x3f3f3f3f
#endif
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
#define cmlSEGMIN
#define cmlSEGMAX
#define cmlSEGSUM
class SegTreeAl{
#ifdef cmlSEGMIN
	int minn[1000005<<2];
#endif
#ifdef cmlSEGMAX
	int maxn[1000005<<2];
#endif
#ifdef cmlSEGSUM
	int sum[1000005<<2];
#endif
	int tag[1000005<<2];
#ifdef cmlSEGSUM
	void pushdown(int o,int l,int r)
#else 
	void pushdown(int o)
#endif
	{
		int&t=tag[o];
#ifdef cmlSEGMIN
		minn[o<<1]+=t;
		minn[o<<1|1]+=t;
#endif
#ifdef cmlSEGMAX
		maxn[o<<1]+=t;
		maxn[o<<1|1]+=t;
#endif
#ifdef cmlSEGSUM
		int m=l+r>>1;
		sum[o<<1]+=t*(m-l+1);
		sum[o<<1|1]+=t*(r-m);
#endif
		tag[o<<1]+=t;
		tag[o<<1|1]+=t;
		t=0;
	}
	void add(int o,int l,int r,int L,int R,int v)
	{
		if(L<=l&&r<=R)
		{
#ifdef cmlSEGMAX
			maxn[o]+=v;
#endif
#ifdef cmlSEGMIN
			minn[o]+=v;
#endif
#ifdef cmlSEGSUM
			sum[o]+=v*(r-l+1);
#endif
			tag[o]+=v;
			return;
		}
		int m=l+r>>1;
#ifdef cmlSEGSUM
		pushdown(o,l,r);
#else
		pushdown(o);
#endif
		if(L<=m)add(o<<1,l,m,L,R,v);
		if(m<R)add(o<<1|1,m+1,r,L,R,v);
#ifdef cmlSEGMAX
		maxn[o]=max(maxn[o<<1],maxn[o<<1|1]);
#endif
#ifdef cmlSEGMIN
		minn[o]=min(minn[o<<1],minn[o<<1|1]);
#endif
#ifdef cmlSEGSUM
		sum[o]=sum[o<<1]+sum[o<<1|1];
#endif
	}
#ifdef cmlSEGMIN
	int qmin(int o,int l,int r,int L,int R)
	{
		if(L<=l&&r<=R)
		{
			return minn[o];
		}
		int m=l+r>>1,res=inf;
#ifdef cmlSEGSUM
		pushdown(o,l,r);
#else
		pushdown(o);
#endif
		if(L<=m)res=min(res,qmin(o<<1,l,m,L,R));
		if(m<R)res=min(res,qmin(o<<1|1,m+1,r,L,R));
#ifdef cmlSEGMAX
		maxn[o]=max(maxn[o<<1],maxn[o<<1|1]);
#endif
#ifdef cmlSEGMIN
		minn[o]=min(minn[o<<1],minn[o<<1|1]);
#endif
#ifdef cmlSEGSUM
		sum[o]=sum[o<<1]+sum[o<<1|1];
#endif
		return res;
	}
#endif

#ifdef cmlSEGMAX
	int qmax(int o,int l,int r,int L,int R)
	{
		if(L<=l&&r<=R)
		{
			return maxn[o];
		}
		int m=l+r>>1,res=-inf;
#ifdef cmlSEGSUM
		pushdown(o,l,r);
#else
		pushdown(o);
#endif
		if(L<=m)res=max(res,qmax(o<<1,l,m,L,R));
		if(m<R)res=max(res,qmax(o<<1|1,m+1,r,L,R));
#ifdef cmlSEGMAX
		maxn[o]=max(maxn[o<<1],maxn[o<<1|1]);
#endif
#ifdef cmlSEGMIN
		minn[o]=min(minn[o<<1],minn[o<<1|1]);
#endif
#ifdef cmlSEGSUM
		sum[o]=sum[o<<1]+sum[o<<1|1];
#endif
		return res;
	}
#endif

#ifdef cmlSEGSUM
	int qsum(int o,int l,int r,int L,int R)
	{
		if(L<=l&&r<=R)
		{
			return sum[o];
		}
		int m=l+r>>1,res=0;
#ifdef cmlSEGSUM
		pushdown(o,l,r);
#else
		pushdown(o);
#endif
		if(L<=m)res+=qsum(o<<1,l,m,L,R);
		if(m<R)res+=qsum(o<<1|1,m+1,r,L,R);
#ifdef cmlSEGMAX
		maxn[o]=max(maxn[o<<1],maxn[o<<1|1]);
#endif
#ifdef cmlSEGMIN
		minn[o]=min(minn[o<<1],minn[o<<1|1]);
#endif
#ifdef cmlSEGSUM
		sum[o]=sum[o<<1]+sum[o<<1|1];
#endif
		return res;
	}
#endif
};
#define newe(n) struct Edge{int v,w,nxt;}e[2*n+5];\
typedef int arr[n+5];\
arr h;\
int cnt=1;\
inline void addedge(int u,int v,int w){e[cnt]=(Edge){v,w,h[u]};h[u]=cnt++;}\
struct node{\
	int u,d;\
	bool operator<(const node&b)const{return d>b.d;}\
};\
void dij(int s,int *d,int N)\
{\
	memset(d,0x3f,sizeof(int)*(N+3));\
	d[s]=0;std::priority_queue<node>q;q.push((node){s,0});\
	while(!q.empty())\
	{\
		int u=q.top().u,D=q.top().d;q.pop();if(D!=d[u])continue;\
		for(int i=h[u];i;i=e[i].nxt){int v=e[i].v,w=e[i].w;\
		if(d[u]+w<d[v])d[v]=d[u]+w,q.push((node){v,d[v]});\
		}\
	}\
}
#define mgs int fa[1<<22],sz[1<<22];\
inline int f(int x){return x==fa[x]?x:fa[x]=f(fa[x]);}\
inline int uf(int x,int y)\
{\
    int fx=f(x),fy=f(y);\
    if(fx==fy)return 0;\
    if(sz[fx]>sz[fy])fx^=fy^=fx^=fy;\
    fa[fx]=fy,sz[fy]+=sz[fx];\
    return 1;\
}
inline int read()
{
    int num=0,f=1;char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>47&&c<58)num=num*10+(c^48),c=getchar();
    return num*f;
}
inline int re1d()
{
    char c=getchar();
    while(c<48||c>49)c=getchar();
    return c&1;
}
#ifdef cmlBIT
struct BIT{int a[1<<20|1],n;
void add(int x,int p){while(x<=n)a[x]+=p,x+=x&-x;}
int operator[](int x){int res=0;while(x)res+=a[x],x-=x&-x;return res;}
int operator()(int l,int r){return (*this)[r]-(*this)[l-1];}};
#endif
int rnv[1000005];
// #define COMB
#ifdef COMB
#ifndef int
#define int long long
#endif
int fac[1000005],inv[1000005];
#endif
void initprog()
{
#ifdef COMB
	fac[0]=inv[0]=inv[1]=1;
	rg(1000000)fac[i]=fac[i-1]*i%mod;gr
	rg(1000000)if(i>1)inv[i]=inv[mod%i]*(mod-mod/i)%mod;gr
	rg(1000000)rnv[i]=inv[i];gr
	rg(1000000)inv[i]=inv[i]*inv[i-1]%mod;gr
#endif
}
#ifdef COMB
int C(int n,int m)
{
	if(n==m||m==0)return 1;
	if(n<m)return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
#endif
inline int qp(int a,int b){int c=1;while(b){if(b&1)c=c*a%mod;a=a*a%mod;b>>=1;}return c;}
inline int mae(int &a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int mde(int &a,int b){a+=mod-b;if(a>=mod)a-=mod;return a;}
inline int mle(int &a,int b){a=a*b%mod;return a;}
inline int mve(int &a,int b){a=a*qp(b,mod-2)%mod;return a;}
inline int mxe(int &a,int b){return a=a>b?a:b;}
inline int mne(int &a,int b){return a=a<b?a:b;}
inline int ae(int a,int b){int c=a+b;return c>=mod?c-mod:c;}
inline int de(int a,int b){return ae(a,mod-b);}
inline int me(int a,int b){return a*b%mod;}
inline int mive(int &a,int b){a=a*rnv[b]%mod;return a;}
inline int ive(int a,int b){return a*rnv[b]%mod;}
inline int ve(int a,int b){return a*qp(b,mod-2)%mod;}
#ifdef cmlST
struct STmin{
	int a[21][1000005],n;
	void init(int N,int *b)
	{
		n=N;
		rg(n)a[0][i]=b[i];gr
		rg(20)rg_(j,n-(1<<i)+1)a[i][j]=min(a[i-1][j],a[i-1][j+(1<<i-1)]);gr gr
	}
	int q(int l,int r)
	{
		int d=std::__lg(r-l+1);
		return min(a[d][l],a[d][r-(1<<d)+1]);
	}
};
struct STmax{
	int a[21][1000005],n;
	void init(int N,int *b)
	{
		n=N;
		rg(n)a[0][i]=b[i];gr
		rg(20)rg_(j,n-(1<<i)+1)a[i][j]=max(a[i-1][j],a[i-1][j+(1<<i-1)]);gr gr
	}
	int q(int l,int r)
	{
		int d=std::__lg(r-l+1);
		return max(a[d][l],a[d][r-(1<<d)+1]);
	}
};
#endif
#ifdef cmlSAM
struct SAM{
	int ch[1000005][26],lnk[1000005],len[1000005],lst=1,cc=1;
	int sz[1000005];
	void insert(int c)
	{
		len[++cc]=len[lst]+1;sz[cc]=1;
		int p=lst;lst=cc;
		while(p&&ch[p][c]==0)ch[p][c]=cc,p=lnk[p];
		if(p==0)lnk[cc]=1;
		else
		{
			int x=ch[p][c];
			if(len[p]+1==len[x])lnk[cc]=x;
			else
			{
				int q=cc;++cc;
				lnk[cc]=lnk[x];
				lnk[x]=lnk[q]=cc;
				len[cc]=len[p]+1;
				memcpy(ch[cc],ch[x],sizeof(ch[cc]));
				while(p&&ch[p][c]==x)ch[p][c]=cc,p=lnk[p];
			}
		}
	}
	newe(1000005);
	long long ans;
	void build()
	{
		rg(cc)addedge(lnk[i],i,0);gr
	}
	void dfs(int u)
	{
		fe(u)dfs(v),sz[u]+=sz[v];gr
		if(sz[u]>1)ans=max(ans,1ll*sz[u]*len[u]);
	}
}t;
#endif
#define pb push_back
using std::vector;
using bot=vector<int>;
// #define printf(...) 0
// #define puts(...) 0
int v[1000005];
signed min_cardinality(signed n)
{
	int DN=0;
	rrg(n)move_inside(i);
	if(press_button()>1)move_outside(i);
	else v[i]=1,DN++;
	gr
	int l=2,r=n/DN,ans=1,cc=DN;
	// odl(DN);
	while(l<=r)
	{
		// odb(DN),odp(l,r);
		int m=l+r+(rand()%2)>>1;
		mne(m,r);
		int bnt=cc;
		bot q,chao;
		rrg(n)if(v[i])continue;
		int ccc=0;
		for(int j=i;j<n;j++)ccc+=!v[j];
		if(bnt+ccc<m*DN)break;
		move_inside(i);
		if(press_button()>m)move_outside(i),chao.pb(i);
		else q.pb(i),bnt++;
		gr
		// odl(cc);
		// odl(bnt);
		if(bnt==m*DN)
		{
			ans=m,l=m+1;
			cc=bnt;
			for(auto x:q)v[x]=1;
		}
		else 
		{
			for(auto x:q)move_outside(x);
			for(auto x:chao)v[x]=1;
			r=m-1;
		}
	}
#undef printf
#undef puts

#ifdef LOCAL
//DO DEBUG
#endif
	return ans;
}
#ifdef LOCAL
signed main()
{
	
}
#endif

Compilation message

insects.cpp: In member function 'void SegTreeAl::pushdown(long long int, long long int, long long int)':
insects.cpp:187:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  187 |   int m=l+r>>1;
      |         ~^~
insects.cpp: In member function 'void SegTreeAl::add(long long int, long long int, long long int, long long int, long long int, long long int)':
insects.cpp:211:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  211 |   int m=l+r>>1;
      |         ~^~
insects.cpp: In member function 'long long int SegTreeAl::qmin(long long int, long long int, long long int, long long int, long long int)':
insects.cpp:236:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  236 |   int m=l+r>>1,res=inf;
      |         ~^~
insects.cpp: In member function 'long long int SegTreeAl::qmax(long long int, long long int, long long int, long long int, long long int)':
insects.cpp:264:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  264 |   int m=l+r>>1,res=-inf;
      |         ~^~
insects.cpp: In member function 'long long int SegTreeAl::qsum(long long int, long long int, long long int, long long int, long long int)':
insects.cpp:292:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  292 |   int m=l+r>>1,res=0;
      |         ~^~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:488:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  488 |   int m=l+r+(rand()%2)>>1;
      |         ~~~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 4 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Correct 3 ms 208 KB Output is correct
9 Correct 4 ms 208 KB Output is correct
10 Correct 5 ms 208 KB Output is correct
11 Correct 4 ms 208 KB Output is correct
12 Correct 6 ms 296 KB Output is correct
13 Correct 6 ms 208 KB Output is correct
14 Correct 4 ms 208 KB Output is correct
15 Correct 5 ms 208 KB Output is correct
16 Correct 4 ms 292 KB Output is correct
17 Correct 5 ms 208 KB Output is correct
18 Correct 5 ms 292 KB Output is correct
19 Correct 5 ms 208 KB Output is correct
20 Correct 3 ms 300 KB Output is correct
21 Correct 4 ms 208 KB Output is correct
22 Correct 2 ms 208 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 4 ms 208 KB Output is correct
7 Correct 2 ms 208 KB Output is correct
8 Correct 3 ms 208 KB Output is correct
9 Correct 4 ms 208 KB Output is correct
10 Correct 5 ms 208 KB Output is correct
11 Correct 4 ms 208 KB Output is correct
12 Correct 6 ms 296 KB Output is correct
13 Correct 6 ms 208 KB Output is correct
14 Correct 4 ms 208 KB Output is correct
15 Correct 5 ms 208 KB Output is correct
16 Correct 4 ms 292 KB Output is correct
17 Correct 5 ms 208 KB Output is correct
18 Correct 5 ms 292 KB Output is correct
19 Correct 5 ms 208 KB Output is correct
20 Correct 3 ms 300 KB Output is correct
21 Correct 4 ms 208 KB Output is correct
22 Correct 2 ms 208 KB Output is correct
23 Correct 16 ms 288 KB Output is correct
24 Correct 8 ms 292 KB Output is correct
25 Correct 30 ms 284 KB Output is correct
26 Correct 22 ms 208 KB Output is correct
27 Correct 11 ms 300 KB Output is correct
28 Correct 7 ms 300 KB Output is correct
29 Correct 25 ms 292 KB Output is correct
30 Correct 27 ms 292 KB Output is correct
31 Correct 30 ms 280 KB Output is correct
32 Correct 29 ms 288 KB Output is correct
33 Correct 12 ms 296 KB Output is correct
34 Correct 27 ms 288 KB Output is correct
35 Correct 25 ms 292 KB Output is correct
36 Correct 30 ms 288 KB Output is correct
37 Correct 22 ms 208 KB Output is correct
38 Correct 25 ms 408 KB Output is correct
39 Correct 17 ms 292 KB Output is correct
40 Correct 14 ms 292 KB Output is correct
41 Correct 7 ms 208 KB Output is correct

Subtask #3
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 0 ms 208 KB Output is correct
6 Correct 0 ms 208 KB Output is correct
7 Correct 47 ms 280 KB Output is correct
8 Correct 19 ms 208 KB Output is correct
9 Correct 30 ms 312 KB Output is correct
10 Correct 50 ms 272 KB Output is correct
11 Correct 53 ms 208 KB Output is correct
12 Correct 19 ms 276 KB Output is correct
13 Correct 56 ms 312 KB Output is correct
14 Correct 38 ms 296 KB Output is correct
15 Correct 46 ms 408 KB Output is correct
16 Correct 48 ms 316 KB Output is correct
17 Correct 74 ms 316 KB Output is correct
18 Correct 57 ms 212 KB Output is correct
19 Correct 26 ms 460 KB Output is correct
20 Correct 69 ms 404 KB Output is correct
21 Correct 56 ms 308 KB Output is correct
22 Correct 56 ms 208 KB Output is correct
23 Correct 53 ms 304 KB Output is correct
24 Correct 36 ms 304 KB Output is correct
25 Correct 21 ms 300 KB Output is correct
26 Correct 13 ms 296 KB Output is correct
27 Correct 53 ms 308 KB Output is correct
28 Correct 59 ms 424 KB Output is correct
29 Correct 54 ms 272 KB Output is correct
30 Correct 59 ms 208 KB Output is correct
31 Correct 44 ms 312 KB Output is correct
32 Correct 56 ms 420 KB Output is correct
33 Correct 53 ms 396 KB Output is correct
34 Correct 59 ms 284 KB Output is correct
35 Correct 47 ms 272 KB Output is correct
36 Correct 55 ms 404 KB Output is correct
37 Correct 50 ms 348 KB Output is correct
38 Correct 46 ms 312 KB Output is correct
39 Correct 52 ms 288 KB Output is correct
40 Correct 54 ms 416 KB Output is correct
41 Correct 41 ms 420 KB Output is correct
42 Correct 58 ms 312 KB Output is correct
43 Correct 15 ms 296 KB Output is correct
44 Correct 37 ms 288 KB Output is correct
45 Correct 57 ms 412 KB Output is correct
46 Correct 20 ms 208 KB Output is correct
47 Correct 19 ms 296 KB Output is correct
48 Correct 16 ms 300 KB Output is correct