QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#80616#5173. 染色ytczy6660 768ms183044kbC++141.7kb2023-02-24 14:34:292023-02-24 14:34:32

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-24 14:34:32]
  • 评测
  • 测评结果:0
  • 用时:768ms
  • 内存:183044kb
  • [2023-02-24 14:34:29]
  • 提交

answer

#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::min;
using std::max;
using std::set;
using std::queue;
using std::sort;
using std::unique;
using std::vector;
using std::pair;
#define ll long long
#define db double
#define inf 0x3f3f3f3f
#define ull unsigned long long
#define F(i,l,r) for(int i=(l);i<=(r);i++)
#define UF(i,l,r) for(int i=(l);i>=(r);i--)
#define mp std::make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define ls(x) x<<1
#define rs(x) x<<1|1
#define pb push_back
inline int rd(){
	int f=1,x=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
	return f*x;
}
const int N=1000010;

int n,m,a[N],pre[N],las[N],nxt[N],f[N][20],g[N][20],tag1[N],tag2[N];
int main(){
    n=rd();m=rd();
    F(i,1,n){
        a[i]=rd();pre[i]=las[a[i]];
        las[a[i]]=i;
    }
    F(i,1,n)las[i]=n+1;
    UF(i,n,1){
        nxt[i]=las[a[i]];
        las[a[i]]=i;
    }
    F(i,1,n+1)tag1[i]=n+1;
    UF(i,n,1)tag1[pre[i]]=i;
    UF(i,n,1)tag1[i]=min(tag1[i],tag1[i+1]);
    F(i,1,n)if(tag1[i]==n+1)tag1[i]=0;
    F(i,1,n)tag2[nxt[i]]=i;
    F(i,1,n)tag2[i]=max(tag2[i],tag2[i-1]);
    F(i,1,n)f[i][0]=tag1[i],g[i][0]=tag2[i];
    F(j,1,19)F(i,1,n-(1<<j)+1)f[i][j]=f[f[i][j-1]][j-1],g[i][j]=g[g[i][j-1]][j-1];
    while(m--){
        int l=rd(),r=rd(),len=abs(r-l),ans=0;
        if(l<=r){
            UF(i,19,0)if(f[l][i]<=r&&f[l][i])l=f[l][i],ans+=(1<<i);
            cout<<len*2-ans<<"\n";
        }
        else{
            UF(i,19,0)if(g[l][i]>=r&&g[l][i])l=g[l][i],ans+=(1<<i);
            cout<<len*2-ans<<"\n";
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 21876kb

input:

10000 100
84 85 52 2 78 53 20 21 23 76 37 44 18 5 37 8 81 65 46 58 69 1 69 37 53 46 37 35 35 89 1 77 35 6 46 59 89 46 25 55 50 38 61 67 44 23 29 24 46 4 42 15 34 77 20 34 83 79 12 50 69 26 38 14 9 66 80 72 22 26 9 68 35 38 19 84 92 30 83 62 100 71 81 60 7 37 64 50 33 60 86 75 45 78 32 53 3 48 87 60 ...

output:

3668
4575
5976
8382
729
7013
183
7320
492
1140
253
2249
13226
6254
456
7507
2162
10481
1791
2675
4801
293
5997
627
6654
6179
11414
2712
3157
7836
18415
511
5486
17835
9564
6147
4996
14577
670
463
15613
12669
8872
7833
10987
6603
6399
5023
9102
8529
2173
10299
2694
12537
4958
2144
8809
1907
6476
2828...

result:

wrong answer 31st words differ - expected: '17782', found: '18415'

Subtask #2:

score: 0
Wrong Answer

Test #7:

score: 0
Wrong Answer
time: 53ms
memory: 32792kb

input:

100000 100000
3 2 3 3 3 3 2 3 2 1 3 1 1 1 3 2 1 3 1 2 2 1 3 1 2 2 1 1 1 3 2 1 3 3 3 3 1 1 1 2 3 3 2 1 1 1 3 1 3 1 3 2 1 3 2 3 3 2 3 3 2 3 3 3 3 3 2 3 2 3 1 3 3 3 3 3 3 3 1 2 3 3 1 3 1 1 2 2 3 1 1 2 3 2 3 1 3 2 1 3 2 3 2 1 1 3 3 1 3 1 2 2 2 3 2 3 2 3 2 1 1 3 1 3 2 2 3 3 3 1 2 2 3 3 2 1 3 1 2 2 2 3 2 ...

output:

121397
133099
54921
6483
9199
90289
111517
29192
38941
119249
66619
7226
66019
42776
44640
49274
11102
107722
89373
12469
4735
87161
46860
102907
36853
10951
12237
59513
18641
55105
11626
7850
5521
38727
67276
58326
16941
70130
70341
53673
51864
551
18481
146863
4016
43296
62515
33972
9870
24982
332...

result:

wrong answer 1st words differ - expected: '113194', found: '121397'

Subtask #3:

score: 0
Wrong Answer

Test #15:

score: 0
Wrong Answer
time: 1ms
memory: 17732kb

input:

5000 5000
256 63 197 36 75 66 33 72 27 75 66 248 29 166 209 252 141 95 84 226 147 249 116 94 192 256 199 273 182 166 116 274 27 211 154 144 283 23 53 110 215 11 164 284 161 221 251 96 43 47 18 115 12 51 156 61 116 209 93 98 47 165 174 106 83 67 184 75 12 290 183 197 112 240 67 56 215 148 104 5 141 2...

output:

1322
2696
1743
2611
4759
4995
2950
1327
880
5076
7873
4860
935
925
808
7270
7663
5325
3813
3295
4478
1577
2540
40
901
300
4351
3882
3813
5739
4610
1658
437
1416
3623
5257
565
119
2044
7615
9112
2047
3121
3683
2883
420
727
4006
179
3231
1443
1602
7127
3008
5954
8083
1539
3807
363
4476
3300
1741
818
2...

result:

wrong answer 11th words differ - expected: '7811', found: '7873'

Subtask #4:

score: 0
Wrong Answer

Test #23:

score: 0
Wrong Answer
time: 768ms
memory: 183044kb

input:

1000000 1000000
1105 3246 1880 3554 818 2331 2576 4140 149 4562 3498 3536 3400 4788 4363 4742 1216 4218 4032 1701 1489 4889 1761 3022 3145 4945 3067 4304 5016 4624 1612 13 1335 3613 1086 2210 386 3464 1156 3352 4341 5006 3465 3900 622 654 1826 2983 1250 4164 3335 4308 2995 1982 1347 4335 2535 5054 4...

output:

1263815
308608
760115
79452
160350
576908
988222
1716103
1345118
215185
615960
546263
1385912
320711
1094276
52291
276158
227555
2476
147750
144806
667128
25418
223778
184324
1445226
1666310
547639
146406
969316
1106498
237554
817297
112491
84810
1188701
316694
717959
169528
559867
767792
412202
732...

result:

wrong answer 97th words differ - expected: '1856186', found: '1858435'