QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#647773#7434. 冷たい部屋、一人piggy123WA 4ms42504kbC++208.5kb2024-10-17 15:38:112024-10-17 15:38:16

Judging History

你现在查看的是最新测评结果

  • [2024-10-17 15:38:16]
  • 评测
  • 测评结果：WA
  • 用时：4ms
  • 内存：42504kb
查看
  • [2024-10-17 15:38:11]
  • 提交

answer

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

ll a[500005],lg[500005],ans[500005],n,m;
int b[20][500005],c[20][500005];
struct qry {
	ll l,r,id;
} p[500005],p2[500005];
vector<int> col[500005];
vector<pair<int,int>> CC[500005];
const ll S=3000;
ll S2=0;

struct block {
	const ll B=800;
	int tag[805],z[500005];
	void add(ll pos,ll v) {
		z[pos]+=v;
		tag[(pos-1)/B+1]+=v;
	}
	ll query(ll pos) {
		ll v=(pos-1)/B+1,r=(n-1)/B+1,ans=0;
		for (ll i=v+1; i<=r; i++)ans+=tag[i];
		for (ll i=pos; i<=v*B; i++)ans+=z[i];
		return ans;
	}
} B;

inline ll getmx(ll l,ll r) {
	ll k=lg[r-l+1];
	return max(c[k][l],c[k][r-(1<<k)+1]);
}

inline ll getmi(ll l,ll r) {
	ll k=lg[r-l+1];
	return min(b[k][l],b[k][r-(1<<k)+1]);
}

int v[1000005],cnt[1000005],d[1000005],nxt[1000005],to[1000005],T;
vector<qry> Q[1000005];

struct CHAIN {
	int vis[1000005],ano[1000005],top;
	array<ll,3> stk[1000005];
	ll gx;
	inline void init(ll len) {
		for (ll i=0; i<=len; i++)vis[i]=0,ano[i]=i;
		top=0,gx=0;
	}

	inline void link(ll a) {
		ll l=ano[a],r=ano[a+1];
		gx+=(a-l+1)*(r-a);
		ano[l]=r,ano[r]=l;
		stk[++top]= {l,r,a};
//		cout<<"?" <<a<<" "<< sz[a]<<" "<<sz[a+1]<<"\n";

	}

	inline void add(ll pos) {
		vis[d[pos]]++;
		if (vis[d[pos]]==2) {
			link(d[pos]);
		}
	}
	inline void del(ll pos) {
		vis[d[pos]]--;
		if (vis[d[pos]]==1) {
			redo(d[pos]);
		}
	}
	inline void redo(ll d) {
		auto tp=stk[top--];
		gx-=(tp[2]-tp[0]+1)*(tp[1]-tp[2]);
		ano[tp[0]]=tp[2];
		ano[tp[1]]=tp[2]+1;
	}
} C;

namespace ly {
	namespace IO {
#define SIZE (1<<25)
		char in[SIZE],out[SIZE],*P1=in,*P2=in,*P3=out;
#define getchar() (P1==P2&&(P2=(P1=in)+fread(in,1,SIZE,stdin),P1==P2)?EOF:*P1++)
#define flush() (fwrite(P3=out,1,SIZE,stdout))
#define putchar(ch) (P3==out+SIZE&&flush(),*P3++=(ch))
		class Flush {
			public:
				~Flush() {
					flush();
				}
		} _;
		template<typename type>
		inline void read(type &x) {
			x=0;
			char ch=getchar();
			while(!isdigit(ch)) ch=getchar();
			while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		}
		template<typename type>
		inline void write(type x) {
			static short Stack[30],top(0);
			do Stack[++top]=x%10,x/=10;
			while(x);
			while(top) putchar(Stack[top--]|48);
			putchar('\n');
		}
#undef SIZE
#undef getchar
#undef putchar
#undef flush
	}
} using namespace ly::IO;

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	read(n),read(m);
	for (ll i=1; i<=n; i++) {
		read(a[i]);
		col[a[i]].push_back(i);
	}
	for (ll i=1; i<=n; i++) {
		if (i>1)lg[i]=lg[i>>1]+1;
		read(b[0][i]);
		c[0][i]=b[0][i];
	}
	for (ll i=1; i<=19; i++) {
		for (ll j=1; j+(1ll<<i)-1<=n; j++) {
			b[i][j]=min(b[i-1][j],b[i-1][j+(1ll<<(i-1))]);
			c[i][j]=max(c[i-1][j],c[i-1][j+(1ll<<(i-1))]);
		}
	}
	for (ll i=1; i<=m; i++) {
		read(p[i].l),read(p[i].r);
		p[i].id=i;
	}

	for (ll i=1; i<=n; i++) {
		if (col[i].size()<=S) {
			for (ll j=0; j+1<(ll)col[i].size(); j++) {
				CC[getmx(col[i][j],col[i][j+1])].push_back({i,j});
//				for (ll k=j+1; k<(ll)col[i].size(); k++) {
//					ll mi=getmi(col[i][j],col[i][k]),mx=getmx(col[i][j],col[i][k]);
////					CC[.emplace_back(mi);
//					++TT;
//					V[TT]=mi;
//					nxt1[TT]=head[mx];
//					head[mx]=TT;
//
//				}
			}
		}
	}
	sort(p+1,p+1+m,[](qry a,qry b) {
		return a.r<b.r;
	});
	ll ps=0;
	for (ll i=1; i<=m; i++) {
		while (ps+1<=n&&ps+1<=p[i].r) {
			for (pair<ll,ll> j:CC[ps+1]) {
				ll mi=getmi(col[j.first][j.second],col[j.first][j.second+1]),mx=ps+1;
				for (ll k=j.second; k>=0; k--) {
					ll pmi=mi,pmx=mx;
					for (ll l=j.second+1; l+1<=col[j.first].size(); l++) {
						if (l==j.second+1){
							
						}else{
							ll tmx=getmx(col[j.first][l-1],col[j.first][l]),tmi=getmi(col[j.first][l-1],col[j.first][l]);
							if (tmx>=pmx)break;
							pmx=max(pmx,tmx);
							pmi=min(pmi,tmi);
						}
						if (pmx!=ps+1)break;
						B.add(pmi,1);
					}
					if (k!=0) {
						mx=max(mx,getmx(col[j.first][k-1],col[j.first][k]));
						mi=min(mi,getmi(col[j.first][k-1],col[j.first][k]));
					}
					if (mx!=ps+1)break;
				}
			}
			ps++;
		}
		ans[p[i].id]+=B.query(p[i].l);
	}
	for (ll i=1; i<=n; i++) {
		if (col[i].size()>S) {
			T=i;
			ll N=col[i].size();
			vector<ll> book;
			for (ll j=0; j+1<N; j++) {
				ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
				book.push_back(mi);
				book.push_back(mx);
			}
			sort(book.begin(),book.end());
			book.erase(unique(book.begin(),book.end()),book.end());
			for (ll j=0; j+1<N; j++) {
				ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
				++cnt[lower_bound(book.begin(),book.end(),mi)-book.begin()+1];
				++cnt[lower_bound(book.begin(),book.end(),mx)-book.begin()+1];
			}
			for (ll j=1; j<=(ll)book.size(); j++)cnt[j]+=cnt[j-1];
			ll lim=cnt[book.size()];
			for (ll j=0; j+1<N; j++) {
				ll mi=getmi(col[i][j],col[i][j+1]),mx=getmx(col[i][j],col[i][j+1]);
				ll mip=lower_bound(book.begin(),book.end(),mi)-book.begin()+1;
				ll mxp=lower_bound(book.begin(),book.end(),mx)-book.begin()+1;
				d[cnt[mip]--]=j;
				to[cnt[mip]+1]=mi;
				d[cnt[mxp]--]=j;
				to[cnt[mxp]+1]=mx;
			}
			ll ps=0;
			for (ll j=1; j<=n; j++) {
				while (ps+1<=lim&&to[ps+1]<=j)ps++;
				nxt[j]=ps;
			}
			S2=0.7*lim/sqrt(m)+1;
			for (ll j=1; j<=m; j++) {
				p2[j].l=nxt[p[j].l-1]+1,p2[j].r=nxt[p[j].r],p2[j].id=p[j].id;
				if (p2[j].l<=p2[j].r) {
					if ((p2[j].l-1)/S2==(p2[j].r-1)/S2) {
						C.init(N);
						for (ll k=p2[j].l; k<=p2[j].r; k++) {
							C.add(k);
						}
						ans[p2[j].id]+=C.gx;
					} else {
						Q[(p2[j].l-1)/S2+1].push_back(p2[j]);
					}
				}

			}
			for (ll j=1; j<=(lim-1)/S2+1; j++) {
				if (!Q[j].size())continue;
				ll lb=j*S2;
				C.init(N);
				ll L=lb+1,R=lb;
//				cout<<(j-1)*S2+1<<"~"<<j*S2<<":\n";
				for (qry k:Q[j]) {
//					cout<<k.l<<","<<k.r<<"\n";
					while (R<k.r)C.add(++R);
					while (L>k.l)C.add(--L);
					ans[k.id]+=C.gx;
					while (L<lb+1)C.del(L++);
				}
			}
			for (ll j=0; j<=lim; j++)cnt[j]=to[j]=nxt[j]=d[j]=0,Q[j].clear();
		}
	}
	for (ll i=1; i<=m; i++) {
		write(ans[i]);
	}
	return 0;
}

/*

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　■■■■■　　　　　■■　　　　　　■■■　　　　　■■■　　　■　　　　■　　　　　■　　　　　■■■■　　　　■■■■　　
　■　　　■■　　　　■■　　　　　■　　■■　　　■　　■■　　■　　　　■　　　　■■　　　　　■　　■■　　■■　　■　　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　■■■　　　　■■　　■■　　■　　　■■　
　■　　　　■　　　　■■　　　　■　　　　■　　■　　　　■　　　■　　■　　　　　■■　　　　■　　　■■　　　　　　■■　
　■　　　　■　　　　■■　　　　■　　　　　　　■　　　　　　　　　■■　　　　　　■■　　　　　　　　■■　　　　　　■　　
　■　　　■■　　　　■■　　　　■　　■■■　　■　　■■■　　　　■■　　　　　　■■　　　　　　　■■　　　　　■■■　　
　■■■■■　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　　■■　　　　　　　　■■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■■　　　　　　　　　　■　
　■　　　　　　　　　■■　　　　■　　　　■　　■　　　　■　　　　■■　　　　　　■■　　　　　■　　　　　　■　　　■■　
　■　　　　　　　　　■■　　　　■■　　■■　　■■　　■■　　　　■■　　　　　　■■　　　　■　　　　　　　■■　　■■　
　■　　　　　　　　　■■　　　　　　■■■■　　　　■■■■　　　　■■　　　　　　■■　　　　■■■■■■　　　■■■■　　
*/
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 42504kb

input:

100 100
4 1 5 1 2 1 7 5 3 7 2 3 6 6 5 3 2 2 4 1 6 5 6 2 2 2 7 6 1 3 6 3 5 6 7 6 1 2 3 3 4 2 1 1 5 4 4 3 6 7 1 1 6 1 5 6 2 3 7 4 2 4 6 7 7 3 5 3 7 2 3 3 5 1 4 7 1 2 2 5 2 2 4 3 4 7 2 7 7 3 7 3 6 6 5 4 5 4 7 6
93 52 12 70 25 36 18 37 27 99 68 40 84 3 76 57 60 19 33 41 92 87 58 13 15 43 28 63 64 59 31 ...

output:

1
0
13
71
1
1
3
7
0
0
2
1
3
20
12
6
61
24
1
0
0
2
3
19
0
0
6
2
0
0
4
1
135
0
19
1
1
29
14
39
1
0
1
7
7
0
12
3
0
1
0
1
1
5
0
28
14
19
2
1
0
0
6
5
0
0
2
7
5
1
2
2
0
1
11
1
0
1
0
10
0
0
5
1
33
1
17
2
1
22
20
1
2
0
0
16
0
1
1
15

result:

wrong answer Output contains longer sequence [length = 101], but answer contains 100 elements
English 繁體中文 简体中文

Server Time: 2024-12-03 03:59:44 | OpenSource Project