QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#23306#1877. Matryoshka Dollszfz2RE 9ms6060kbC++145.8kb2022-03-14 20:39:452022-04-30 02:47:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 02:47:14]
  • 评测
  • 测评结果：RE
  • 用时：9ms
  • 内存：6060kb
查看
  • [2022-03-14 20:39:45]
  • 提交

answer

#pragma GCC optimize(2)
//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
//#include <random>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/priority_queue.hpp>
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(register int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(register int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<int,int>
#define cp complex<double>
#define vi vector<int>
#define ull unsigned long long
#define mem0(x) memset(x,0,sizeof(x))
#define mem0x3f(x) memset(x,0x3f,sizeof(x))
using namespace std;
//using namespace __gnu_pbds;
const double Pi=acos(-1);
namespace fastIO {
	template<class T>
	inline void read(T &x) {
		x=0;
		bool fu=0;
		char ch=0;
		while(ch>'9'||ch<'0') {
			ch=getchar();
			if(ch=='-')fu=1;
		}
		while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
		if(fu)x=-x;
	}
	inline int read() {
		int x=0;
		bool fu=0;
		char ch=0;
		while(ch>'9'||ch<'0') {
			ch=getchar();
			if(ch=='-')fu=1;
		}
		while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
		return fu?-x:x;
	}
	template<class T,class... Args>
	inline void read(T& t,Args&... args) {
		read(t);
		read(args...);
	}
	char _n_u_m_[40];
	template<class T>
	inline void write(T x) {
		if(x==0){
			putchar('0');
			return;
		}
		T tmp = x > 0 ? x : -x ;
		if( x < 0 ) putchar('-') ;
		register int cnt = 0 ;
		while( tmp > 0 ) {
			_n_u_m_[ cnt ++ ] = tmp % 10 + '0' ;
			tmp /= 10 ;
		}
		while( cnt > 0 ) putchar(_n_u_m_[ -- cnt ]) ;
	}
	template<class T>
	inline void write(T x ,char ch) {
		write(x);
		putchar(ch);
	}
}
using namespace fastIO;
struct trie{
	unsigned sum1,ch1,sum2[32],ch2[32],sum3[1024],ch3[1024],sum4[1<<15],ch4[1<<15];
	inline void add(int pos){
		++sum4[pos>>5];
		ch4[pos>>5]|=(1u<<(pos&31));
		++sum3[pos>>10];
		ch3[pos>>10]|=(1u<<(pos>>5&31));
		++sum2[pos>>15];
		ch2[pos>>15]|=(1u<<(pos>>10&31));
		++sum1;
		ch1|=(1u<<(pos>>15));
	}
	inline void mns(int pos){
		ch4[pos>>5]^=(1u<<(pos&31));
		if(!(--sum4[pos>>5]))
		ch3[pos>>10]^=(1u<<(pos>>5&31));
		if(!(--sum3[pos>>10]))
		ch2[pos>>15]^=(1u<<(pos>>10&31));
		if(!(--sum2[pos>>15]))
		ch1^=(1u<<(pos>>15));
		--sum1;
	}
	inline int pre(int pos){
		if(ch4[pos>>5]&(1u<<(pos&31))-1){
			return (pos>>5<<5)|31-__builtin_clz(ch4[pos>>5]&(1u<<(pos&31))-1);
		}
		pos>>=5;
		if(ch3[pos>>5]&(1u<<(pos&31))-1){
			pos=(pos>>5<<5)|31-__builtin_clz(ch3[pos>>5]&(1u<<(pos&31))-1);
			return pos<<5|(31-__builtin_clz(ch4[pos]));
		}
		pos>>=5;
		if(ch2[pos>>5]&(1u<<(pos&31))-1){
			pos=(pos>>5<<5)|31-__builtin_clz(ch2[pos>>5]&(1u<<(pos&31))-1);
			pos=pos<<5|(31-__builtin_clz(ch3[pos]));
			return pos<<5|(31-__builtin_clz(ch4[pos]));
		}
		pos>>=5;
		if(ch1&(1u<<(pos&31))-1){
			pos=(pos>>5<<5)|31-__builtin_clz(ch1&(1u<<(pos&31))-1);
			pos=pos<<5|(31-__builtin_clz(ch2[pos]));
			pos=pos<<5|(31-__builtin_clz(ch3[pos]));
			return pos<<5|(31-__builtin_clz(ch4[pos]));
		}
		return 0;
	}
	inline int suf(int pos){
		++pos;
		if(ch4[pos>>5]&(~((1u<<(pos&31))-1))){
			return (pos>>5<<5)|__builtin_ctz(ch4[pos>>5]&(~((1u<<(pos&31))-1)));
		}
		pos>>=5;++pos;
		if(ch3[pos>>5]&(~((1u<<(pos&31))-1))){
			pos=(pos>>5<<5)|__builtin_ctz(ch3[pos>>5]&(~((1u<<(pos&31))-1)));
			return pos<<5|__builtin_ctz(ch4[pos]);
		}
		pos>>=5;++pos;
		if(ch2[pos>>5]&(~((1u<<(pos&31))-1))){
			pos=(pos>>5<<5)|__builtin_ctz(ch2[pos>>5]&(~((1u<<(pos&31))-1)));
			pos=pos<<5|__builtin_ctz(ch3[pos]);
			return pos<<5|__builtin_ctz(ch4[pos]);
		}
		pos>>=5;++pos;
		if(ch1&(~((1u<<(pos&31))-1))){
			pos=(pos>>5<<5)|__builtin_ctz(ch1&(~((1u<<(pos&31))-1)));
			pos=pos<<5|__builtin_ctz(ch2[pos]);
			pos=pos<<5|__builtin_ctz(ch3[pos]);
			return pos<<5|__builtin_ctz(ch4[pos]);
		}
		return 0;
	}
}T;
int n,m,a[500002],p[500002];
int B=900;
struct Q{
	int l,r,id;
}q[500002];
inline bool cmp(const Q &x,const Q &y){
	return ((x.l-1)/B==(y.l-1)/B)?(((x.l-1)/B&1)?x.r<y.r:x.r>y.r):x.l<y.l;
}
ll ans,res[500002];
inline void dbg(){
	while(true){
		int opt=read();
		if(opt==1){
			T.add(read());
		}if(opt==2)T.mns(read());
		if(opt==3)write(T.pre(read()),'\n');
		if(opt==4)write(T.suf(read()),'\n');
	}
}
int main() {//dbg();return 0;
//	freopen("rrads.in","r",stdin);
//	freopen("rrads.out","w",stdout);
	cin>>n>>m;
B=n/sqrt(m);
	F(i,1,n)p[a[i]=read()]=i;
	F(i,1,m){
		read(q[i].l);read(q[i].r);q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	int l=1,r=0,x,y;
	F(i,1,m){
		while(l>q[i].l){
			--l;
			if(x=T.pre(a[l]))ans+=p[x]-l;
			if(y=T.suf(a[l]))ans+=p[y]-l;
			if(x&&y)ans-=(p[x]<p[y]?p[y]-p[x]:p[x]-p[y]);
			T.add(a[l]);//cerr<<l<<" "<<r<<" "<<ans<<endl;
		}
		while(r<q[i].r){
			++r;
			if(x=T.pre(a[r]))ans+=r-p[x];
			if(y=T.suf(a[r]))ans+=r-p[y];
			if(x&&y)ans-=(p[x]<p[y]?p[y]-p[x]:p[x]-p[y]);
			T.add(a[r]);//cerr<<l<<" "<<r<<" "<<ans<<endl;
		}
		while(l<q[i].l){
			if(x=T.pre(a[l]))ans-=p[x]-l;
			if(y=T.suf(a[l]))ans-=p[y]-l;
			if(x&&y)ans+=(p[x]<p[y]?p[y]-p[x]:p[x]-p[y]);
			T.mns(a[l++]);//cerr<<l<<" "<<r<<" "<<ans<<endl;
		}
		while(r>q[i].r){
			if(x=T.pre(a[r]))ans-=r-p[x];
			if(y=T.suf(a[r]))ans-=r-p[y];
			if(x&&y)ans+=(p[x]<p[y]?p[y]-p[x]:p[x]-p[y]);
			T.mns(a[r--]);//cerr<<l<<" "<<r<<" "<<ans<<" "<<x<<" "<<y<<endl;
		}
		res[q[i].id]=ans;
	}
	F(i,1,m)write(res[i],'\n');
	return 0;
}
/*
10
10
1 2 3 4 5 6 7 8 9 10
1 10
2 9
3 8
4 7
5 6
1 5
2 6
3 7
4 8
5 9
*/
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 5676kb

input:

5 5
1 5 2 4 3
1 5
1 4
1 3
1 2
1 1

output:

7
5
3
1
0

result:

ok 5 number(s): "7 5 3 1 0"

Test #2:

score: 0
Accepted
time: 3ms
memory: 5732kb

input:

1 1
1
1 1

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 9ms
memory: 6060kb

input:

100000 1
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 ...

output:

4999950000

result:

ok 1 number(s): "4999950000"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5536kb

input:

20 1
12 8 13 10 18 14 1 19 5 16 15 9 17 20 6 2 11 4 3 7
9 18

output:

36

result:

ok 1 number(s): "36"

Test #5:

score: 0
Accepted
time: 3ms
memory: 5736kb

input:

20 10
5 16 11 7 19 8 12 13 17 18 6 1 14 3 4 2 15 20 10 9
7 11
7 13
7 17
11 15
1 7
4 6
1 5
6 14
3 5
9 9

output:

7
16
34
9
20
3
8
22
3
0

result:

ok 10 numbers

Test #6:

score: 0
Accepted
time: 3ms
memory: 5748kb

input:

20 50
7 3 13 8 9 18 1 15 12 10 20 11 17 16 2 19 5 4 6 14
3 6
5 15
11 20
10 18
9 20
3 17
13 20
16 17
3 20
4 17
15 18
5 19
3 14
8 20
2 20
1 4
15 19
16 20
5 13
14 17
4 10
6 16
8 16
1 12
4 9
11 15
4 20
8 11
3 16
7 7
3 11
3 7
4 4
5 12
6 20
3 14
6 19
6 19
2 14
2 12
5 6
4 6
8 15
10 19
4 14
1 16
1 20
2 13
3...

output:

6
48
36
24
46
74
17
1
104
64
5
68
44
58
130
5
9
8
30
7
13
48
26
38
11
8
92
5
70
0
28
9
0
20
80
44
58
58
48
36
1
2
20
28
34
76
136
46
1
28

result:

ok 50 numbers

Test #7:

score: 0
Accepted
time: 3ms
memory: 5740kb

input:

20 100
4 13 20 8 1 18 19 9 17 5 12 7 11 16 6 3 15 10 14 2
4 19
1 6
6 19
4 6
2 17
1 5
11 13
1 15
9 17
9 15
7 20
3 19
10 19
1 10
11 17
10 17
2 18
17 20
12 19
1 3
5 17
7 13
6 18
10 20
1 6
2 17
5 9
4 13
11 13
2 20
7 13
12 17
5 19
17 20
11 19
3 15
3 5
5 11
1 17
10 15
16 20
1 6
2 19
4 12
5 18
9 17
3 6
12 ...

output:

76
16
57
3
84
10
3
74
31
19
59
80
40
44
16
26
94
5
26
2
54
17
53
44
16
84
8
32
3
106
17
12
68
5
30
48
2
16
102
14
9
16
98
28
64
31
6
1
54
20
26
31
74
5
26
3
66
32
36
59
1
26
6
33
35
5
57
1
1
57
24
6
10
68
36
41
34
0
12
8
11
2
62
12
41
10
5
25
0
60
0
44
25
12
8
2
16
36
8
1

result:

ok 100 numbers

Test #8:

score: 0
Accepted
time: 0ms
memory: 5652kb

input:

20 228
7 3 17 10 16 11 19 5 1 13 20 18 14 2 8 4 6 9 12 15
7 20
2 20
10 13
14 19
1 9
12 20
17 19
9 20
10 12
14 17
4 15
7 16
5 12
13 16
16 18
7 18
1 11
7 17
2 20
6 8
9 17
12 18
7 18
3 4
7 13
1 4
6 12
6 10
3 17
3 4
5 14
7 13
9 20
6 20
2 4
14 17
17 20
1 7
19 20
4 20
14 15
12 16
4 6
4 15
10 11
2 16
2 20
...

output:

66
136
5
9
32
30
2
42
3
5
62
40
28
5
2
50
44
44
136
3
20
14
50
1
16
5
18
10
74
1
44
16
42
90
3
5
3
13
1
108
1
6
3
62
1
94
136
3
14
42
3
80
26
6
54
7
26
26
31
1
74
38
15
14
52
26
14
6
4
7
3
2
70
13
2
44
6
76
26
90
1
66
108
0
28
16
132
18
7
3
14
48
7
15
1
8
9
22
9
18
36
5
70
44
42
3
1
42
0
3
3
8
3
62
...

result:

ok 228 numbers

Test #9:

score: 0
Accepted
time: 2ms
memory: 5684kb

input:

20 322
3 11 4 1 9 19 7 12 5 17 8 15 10 18 13 2 20 16 14 6
8 14
6 6
3 17
3 16
9 18
7 17
12 13
4 14
12 18
6 13
8 9
3 17
7 20
12 16
10 15
12 16
12 14
16 19
6 7
18 20
6 16
7 14
5 19
12 13
3 14
10 15
11 18
12 20
8 9
1 13
17 18
1 18
4 19
4 9
5 19
4 5
1 2
10 17
11 19
7 14
15 20
20 20
4 7
12 15
7 17
3 13
7 ...

output:

19
0
91
80
37
39
1
48
21
23
1
91
81
10
13
10
3
5
1
2
44
23
87
1
50
13
25
37
1
58
1
119
99
14
87
1
1
21
33
23
15
0
6
7
39
42
36
1
91
3
107
25
1
44
1
0
10
7
1
1
55
3
10
2
34
91
1
51
26
25
75
1
1
18
79
13
1
80
21
16
5
3
0
18
3
7
63
63
66
3
0
5
17
0
21
10
1
3
5
1
6
35
41
29
59
43
21
0
45
3
6
75
1
103
0
...

result:

ok 322 numbers

Test #10:

score: -100
Runtime Error

input:

20 1000
16 6 17 1 12 11 5 8 10 19 4 18 2 9 14 7 15 3 20 13
1 6
8 9
9 11
5 18
3 20
2 9
17 18
12 12
12 20
5 17
1 8
10 10
2 9
17 19
1 7
7 15
12 19
2 7
9 14
2 14
1 4
15 17
11 19
2 5
3 12
11 14
11 14
13 17
7 8
9 18
2 11
8 11
1 4
4 8
12 13
12 19
7 16
12 16
11 15
5 9
5 18
2 19
11 15
1 15
4 20
4 9
5 14
5 19...

output:

result:
English 繁體中文 简体中文

Server Time: 2024-11-30 02:34:06 | OpenSource Project