Submission #741339

#	Time	Username	Problem	Language	Result	Execution time	Memory
741339		arnold518	Mizuyokan 2 (JOI23_mizuyokan2)	C++17	0 / 100	4065 ms	17236 KiB

mizuyokan2

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 25e4;
const int INF = 1e9+1;
const int SQ = 500;

int N, Q, A[MAXN+10];

struct SEG
{
	ll tree[MAXN*4+10];
	void update(int node, int tl, int tr, int x)
	{
		if(tl==tr)
		{
			tree[node]=A[x];
			return;
		}
		int mid=tl+tr>>1;
		if(x<=mid) update(node*2, tl, mid, x);
		else update(node*2+1, mid+1, tr, x);
		tree[node]=tree[node*2]+tree[node*2+1];
	}
	ll query(int node, int tl, int tr, int l, int r)
	{
		if(l<=tl && tr<=r) return tree[node];
		if(r<tl || tr<l) return 0;
		int mid=tl+tr>>1;
		return query(node*2, tl, mid, l, r)+query(node*2+1, mid+1, tr, l, r);
	}
	int queryr(int node, int tl, int tr, int l, int r, int &y)
	{
		//printf("!%d %d %d %d %d\n", tl, tr, l, r, y);
		if(r<tl || tr<l) return -1;
		if(l<=tl && tr<=r && tree[node]<=y)
		{
			y-=tree[node];
			return -1;
		}
		if(tl==tr) return tl;
		int mid=tl+tr>>1, ret;
		ret=queryr(node*2, tl, mid, l, r, y);
		if(ret!=-1) return ret;
		ret=queryr(node*2+1, mid+1, tr, l, r, y);
		return ret;
	}
	int queryr(int l, int r, int y)
	{
		int t=queryr(1, 1, N, l, r, y);
		if(t==-1) return INF;
		return t+1;
	}
}seg;

struct SEG2
{
	ll tree[MAXN*4+10], lazy[MAXN*4+10];
	void busy(int node, int tl, int tr)
	{
		if(!lazy[node]) return;
		tree[node]+=lazy[node];
		if(tl!=tr)
		{
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	void update(int node, int tl, int tr, int l, int r, ll k)
	{
		busy(node, tl, tr);
		if(r<tl || tr<l) return;
		if(l<=tl && tr<=r)
		{
			lazy[node]+=k;
			busy(node, tl, tr);
			return;
		}
		int mid=tl+tr>>1;
		update(node*2, tl, mid, l, r, k);
		update(node*2+1, mid+1, tr, l, r, k);
		tree[node]=max(tree[node*2], tree[node*2+1]);
	}
	int query(int node, int tl, int tr, int l, int r, ll y)
	{
		busy(node, tl, tr);
		if(r<tl || tr<l) return -1;
		if(l<=tl && tr<=r && tree[node]<=y) return -1;
		if(tl==tr) return tl;
		int mid=tl+tr>>1, ret;
		ret=query(node*2, tl, mid, l, r, y);
		if(ret!=-1) return ret;
		ret=query(node*2+1, mid+1, tr, l, r, y);
		return ret;
	}
	int query(int l, int r, int y)
	{
		int t=query(1, 1, N, l, r, y);
		return t;
	}
}seg2;

int P[MAXN+10], P2[MAXN+10], Q2[MAXN+10];

int f(int now, int b)
{
	int t=1;
	while(now/SQ<b/SQ)
	{
		if(P2[now]!=-1)
		{
			t+=Q2[now];
			now=P2[now];
		}
		int tt=seg.queryr(now+1, b, A[now]);
		ll s=seg.query(1, 1, N, 1, now);
		now=seg2.query(tt, b, s);
		t++;
		if(now==-1) break;
	}
	while(now!=-1 && now<b)
	{
		//printf("!%d %d\n", now, P[now]);
		if(P[now]!=-1 && P[now]<=b)
		{
			now=P[now];
			t+=2;
		}
		else
		{
			int tt=seg.queryr(now+1, b, A[now]);
			//printf("??%d\n", tt);
			if(tt>b+1) t--;
			else t++;
			break;
		}
	}
	return t;
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);
	
	for(int i=1; i<=N; i++)
	{
		seg.update(1, 1, N, i);
		seg2.update(1, 1, N, i+1, N, A[i]);
		seg2.update(1, 1, N, i, i, -A[i]);
	}

	for(int i=0; i<=N/SQ; i++)
	{
		int l=max(1, i*SQ), r=min(N, i*SQ+SQ-1);
		for(int j=r; j>=l; j--)
		{
			int t=seg.queryr(j+1, r, A[j]);
			ll s=seg.query(1, 1, N, 1, j);
			P[j]=seg2.query(t, r, s);
			if(P[j]==-1) P2[j]=-1, Q2[j]=0;
			else P2[j]=P[P2[j]], Q2[j]=Q2[P[j]]+2;
		}
	}
	//for(int i=1; i<=N; i++) printf("%d ", P[i]); printf("\n");
	//for(int i=1; i<=N; i++) printf("%d ", Q2[i]); printf("\n");

	scanf("%d", &Q);
	while(Q--)
	{
		int x, y, a, b;
		scanf("%d%d%d%d", &x, &y, &a, &b);

		seg2.update(1, 1, N, x+1, N, -A[x]+y);
		seg2.update(1, 1, N, x, x, -y+A[x]);

		A[x]=y; a++;
		seg.update(1, 1, N, x);


		int l=max(1, x/SQ*SQ), r=min(N, x/SQ*SQ+SQ-1);
		for(int j=r; j>=l; j--)
		{
			int t=seg.queryr(j+1, r, A[j]);
			ll s=seg.query(1, 1, N, 1, j);
			P[j]=seg2.query(t, r, s);
			if(P[j]==-1) P2[j]=-1, Q2[j]=0;
			else P2[j]=P[P2[j]], Q2[j]=Q2[P[j]]+2;
		}

		int ans=max(1, f(a, b));
		int t=seg2.query(a, b, seg.query(1, 1, N, 1, a-1));
		if(t!=-1) ans=max(ans, 1+f(t, b));
		printf("%d\n", ans);	
	}
}

Compilation message (stderr)

mizuyokan2.cpp: In member function 'void SEG::update(int, int, int, int)':
mizuyokan2.cpp:24:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int mid=tl+tr>>1;
      |           ~~^~~
mizuyokan2.cpp: In member function 'll SEG::query(int, int, int, int, int)':
mizuyokan2.cpp:33:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid=tl+tr>>1;
      |           ~~^~~
mizuyokan2.cpp: In member function 'int SEG::queryr(int, int, int, int, int, int&)':
mizuyokan2.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int mid=tl+tr>>1, ret;
      |           ~~^~~
mizuyokan2.cpp: In member function 'void SEG2::update(int, int, int, int, int, ll)':
mizuyokan2.cpp:84:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |   int mid=tl+tr>>1;
      |           ~~^~~
mizuyokan2.cpp: In member function 'int SEG2::query(int, int, int, int, int, ll)':
mizuyokan2.cpp:95:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |   int mid=tl+tr>>1, ret;
      |           ~~^~~
mizuyokan2.cpp: In function 'int main()':
mizuyokan2.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
mizuyokan2.cpp:149:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~
mizuyokan2.cpp:173:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
mizuyokan2.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |   scanf("%d%d%d%d", &x, &y, &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11