QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#725767#7626. Quake and RebuildscallionsongWA 559ms4548kbC++144.4kb2024-11-08 19:53:492024-11-08 19:53:50

Judging History

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

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

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,id(i));
        int res=0;
        UF(i,id(n),1){
            if(mp[i].empty()) continue;
            if(i==mi&&(int)mp[i].size()==1) {res++;break;}
            if(chk(i)){
                for(auto j:mp[i]){
                    res+=w3[j.fir];
                    int nxt=max(w2[j.fir]+tag2[i],1);
                    mp[id(nxt)][nxt]=1;
                    chkmin(mi,id(nxt));
                }
            }
            else{
                UF(j,r(i),l(i)) if(mp[i][j]) res++,mp[i][max(w1[j]+tag2[i],1)]=1;
            }
        }
        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: 0ms
memory: 4392kb

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: 4364kb

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: -100
Wrong Answer
time: 559ms
memory: 4548kb

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:

74
73
67
60
58
52
57
52
51
52
50
52
54
50
50
56
55
50
49
54
49
50
53
48
49
48
49
48
53
48
50
53
47
52
45
49
47
46
47
48
49
48
48
48
47
48
47
49
48
50
48
47
48
47
48
48
49
48
47
45
45
46
46
49
47
47
49
46
47
47
46
48
48
47
48
47
46
47
46
47
46
45
47
48
49
50
49
47
48
49
47
47
48
50
46
47
48
46
46
47
...

result:

wrong answer 1st lines differ - expected: '78', found: '74'