QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#725820#7626. Quake and RebuildscallionsongWA 1748ms5316kbC++144.5kb2024-11-08 20:11:452024-11-08 20:11:45

Judging History

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

  • [2024-11-20 20:27:49]
  • hack成功,自动添加数据
  • (/hack/1219)
  • [2024-11-08 20:11:45]
  • 评测
  • 测评结果:WA
  • 用时:1748ms
  • 内存:5316kb
  • [2024-11-08 20:11:45]
  • 提交

answer

bool M1;
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define LL __int128
#define db double
#define LD long double
#define Pii pair<int,int>
#define Pll pair<ll,ll>
#define Pull pair<ull,ull>
#define Pdb pair<db,db>
#define fir first
#define sec second
#define vec vector<int>
#define pb push_back
#define qlr cerr<<"qlr\n"
#define dyh cerr<<"dyh\n"
#define pc(x) __builtin_popcount(x)
#define uni(x,y) uniform_int_distribution<int>(x,y)(rng)
#define unl(x,y) uniform_int_distribution<ll>(x,y)(rng)
#define unr(x,y) uniform_real_distribution<double>(x,y)(rng)
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define look_memory cerr<<'\n'<<abs(&M1-&M2)/1024.0/1024<<'\n'
#define look_time cerr<<'\n'<<clock()*1.0/CLOCKS_PER_SEC<<'\n'
mt19937 rng(time(0)^(*new int));
const int INF=0x3f3f3f3f;
const int Mod=998244353;
template<typename T>
inline void inc(T &a,T b){
	if(b<0) b+=Mod;
	a+=b;
	if(a>=Mod) a-=Mod;
}
template<typename T>
inline void dec(T &a,T b){
	if(b<0) b+=Mod;
	a-=b;
	if(a<0) a+=Mod;
}
template<typename T>
inline void muc(T &a,T b){
	a=a*b%Mod;
}
template<typename T>
inline bool chkmin(T &a,T b){
	if(a<=b) return false;
	a=b;
	return true;
}
template<typename T>
inline bool chkmax(T &a,T b){
	if(a>=b) return false;
	a=b;
	return true;
}
int n,q;
struct Blk{
    #define N 200000
    #define sq 100
    #define B N/sq
    int w1[N+10],w2[N+10],w3[N+10];
    int tag1[B+10],tag2[B+10];
    gp_hash_table<int,int> mp[B+10];
    int id(int x){
        return (x-1)/sq+1;
    }
    int l(int x){
        return (x-1)*sq+1;
    }
    int r(int x){
        return min(x*sq,n);
    }
    void down(int k){
        F(i,l(k),r(k)) w1[i]+=tag2[k];
        tag2[k]=0;
    }
    void update(int k){
        F(i,l(k),r(k)){
            if(id(w1[i])!=k) w2[i]=w1[i],w3[i]=1;
            else w2[i]=w2[w1[i]],w3[i]=w3[w1[i]]+1;
        }
    }
    void build(){
        F(i,1,id(n)) update(i);
    }
    void modify(int k,int x,int y,int z){
        down(k);
        F(i,l(k),r(k)) if(i>=x&&i<=y) w1[i]=max(w1[i]-z,1);
        update(k);
    }
    void change(int x,int y,int z){
        if(id(x)==id(y)){
            modify(id(x),x,y,z);
            return;
        }
        modify(id(x),x,y,z),modify(id(y),x,y,z);
        F(i,id(x)+1,id(y)-1){
            if(tag1[i]<sq) modify(i,x,y,z);
            else tag2[i]-=z;
//            tag1[i]+=z;
        }
    }
    bool chk(int k){
        gp_hash_table<int,int> tg;
        for(auto i:mp[k]){
            int nxt=max(w2[i.fir]+tag2[k],1);
            if(tg[nxt]) return 0;
            tg[nxt]=1;
        }
        return 1;
    }
    int query(vec V){
        F(i,1,id(n)) mp[i].clear();
        int mi=INF; 
        for(auto i:V) mp[id(i)][i]=1,chkmin(mi,i);
        int res=0;
        UF(i,id(n),1){
            if(mp[i].empty()) continue;
            if(chk(i)){
                for(auto j:mp[i]){
                	if(j.fir==mi) {res++;break;}
                    res+=w3[j.fir];
                    int nxt=max(w2[j.fir]+tag2[i],1);
                    mp[id(nxt)][nxt]=1;
                    chkmin(mi,nxt);
                }
            }
            else{
                UF(j,r(i),l(i)){
                	if(!mp[i][j]) continue;
                	if(j==mi) {res++;break;}
					res++;
					int nxt=max(w1[j]+tag2[i],1);
					mp[id(nxt)][nxt]=1;
					chkmin(mi,nxt);
				}
            }
        }
        return res;
    }
    #undef N
    #undef sq
    #undef B
}blk;
bool M2;
int main(){
	// freopen("aminusb.in","r",stdin);
	// freopen("aminusb.out","w",stdout);
	srand(time(0)^(*new int));
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    cin>>n>>q;
    blk.w1[1]=1;
    F(i,2,n) cin>>blk.w1[i];
    blk.build();
    while(q--){
        int op,x,y,z;
        vec V;
        cin>>op;
        if(op==1) cin>>x>>y>>z,blk.change(x,y,z);
        else{
            cin>>x;
            V.resize(x);
            F(i,0,x-1) cin>>V[i];
            cout<<blk.query(V)<<'\n';
        }
    }
	look_memory;
	look_time;
	return 0;
}
/*
g++ B1.cpp -o B1 -std=c++14 -O2&&./B1

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

10 10
1 2 3 3 4 5 7 7 9
1 2 10 3
2 9 9 5 3 10 7 2 4 6 8
1 6 10 3
1 2 7 3
1 7 10 3
2 2 4 3
2 3 7 4 4
1 3 9 3
1 3 9 3
1 10 10 3
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4268kb

input:

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

output:

3
4
3

result:

ok 3 lines

Test #2:

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

input:

10 10
1 2 3 3 4 5 7 7 9
1 2 10 3
2 9 9 5 3 10 7 2 4 6 8
1 6 10 3
1 2 7 3
1 7 10 3
2 2 4 3
2 3 7 4 4
1 3 9 3
1 3 9 3
1 10 10 3

output:

10
3
3

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 891ms
memory: 4536kb

input:

3051 198219
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 4 1 1 1 6 3 1 1 2 2 2 1 6 3 7 3 3 5 1 2 7 2 5 1 3 4 1 6 2 1 2 1 10 3 3 1 3 2 2 6 3 9 3 1 12 5 1 5 6 7 7 3 2 6 5 8 12 3 7 16 3 9 4 7 1 2 13 3 3 5 9 9 9 6 5 4 41 8 7 10 7 2 7 2 4 14 4 3 1 16 2 6 3 10 3 4 9 10 1 6 1 14 6 10 8 9 6 3 1 1 1 13 22 4 20 17 1 15 ...

output:

78
78
70
64
60
55
60
58
52
54
51
53
56
51
51
57
55
52
49
55
49
50
53
49
49
48
49
48
53
50
50
54
47
52
45
49
49
46
47
48
49
50
48
49
47
48
47
49
48
50
48
49
48
47
49
48
51
48
48
45
45
46
50
50
50
48
49
46
47
47
46
48
48
47
49
47
46
47
46
47
46
45
47
49
49
50
51
48
48
49
47
47
48
50
46
47
48
50
46
47
...

result:

ok 13214 lines

Test #4:

score: 0
Accepted
time: 909ms
memory: 4784kb

input:

6173 198631
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...

output:

2819
1049
1155
831
722
5962
123
624
554
601
241
597
81
29
34
390
350
443
385
6038
6083
258
5
315
27
281
6029
300
6136
322
227
46
271
263
26
268
257
6101
5816
255
258
156
243
270
186
6099
16
13
5435
163
7
35
219
182
214
10
24
23
194
178
188
183
200
167
158
197
24
189
131
35
167
24
189
15
183
176
6050...

result:

ok 30261 lines

Test #5:

score: 0
Accepted
time: 1193ms
memory: 4496kb

input:

9724 198809
1 1 1 1 1 1 1 1 1 4 2 2 1 2 1 4 1 5 1 3 4 2 2 4 2 7 4 1 2 6 9 2 1 1 2 3 1 1 3 4 3 1 2 1 18 1 3 4 2 4 4 6 1 4 2 1 7 11 4 1 5 6 2 12 3 4 4 7 1 1 11 4 15 21 3 4 15 1 1 12 11 3 1 1 16 9 14 2 5 9 3 5 9 3 8 5 15 16 9 14 13 8 2 4 5 10 6 1 10 11 10 12 7 4 36 6 5 7 6 13 7 1 14 5 1 6 8 7 1 10 20 6...

output:

24
25
31
31
27
25
29
23
23
21
26
23
21
24
23
23
26
26
21
24
27
23
23
23
20
19
20
18
28
25
26
21
19
21
21
26
20
23
17
20
18
21
22
22
18
21
25
18
17
18
24
18
16
18
19
24
20
18
19
17
17
21
25
19
21
23
19
23
15
17
19
19
22
18
20
18
21
19
18
18
15
16
22
17
17
18
13
16
19
16
15
16
18
16
15
17
15
18
18
20
...

result:

ok 66269 lines

Test #6:

score: -100
Wrong Answer
time: 1748ms
memory: 5316kb

input:

12796 185791
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99...

output:

12100
7532
12357
12774
134
12761
5309
1646
12726
1882
247
78
1660
12229
12143
1499
1368
1273
1387
341
274
1374
1237
1359
112
1152
981
12681
949
890
820
774
62
644
836
925
12
13
1203
666
732
731
1127
12320
11473
82
655
12788
569
5866
621
2798
12114
85
609
11827
1
12455
56
605
575
530
54
645
1845
93
2...

result:

wrong answer 5th lines differ - expected: '211', found: '134'