QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#834701	#9727. Barkley III	remain11	TL	1859ms	198760kb	C++20	6.7kb	2024-12-27 21:42:01	2024-12-27 21:42:02

Judging History

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

[2025-01-13 03:55:43]
hack成功，自动添加数据
(/hack/1447)

[2024-12-27 21:42:02]
评测

测评结果：TL
用时：1859ms
内存：198760kb

查看

[2024-12-27 21:42:01]
提交

answer

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = double;
using ull = unsigned long long;

constexpr int N = 3e5 + 5;
const ll inf = 1e16;

template<class T>
T& cmax(T &a, const T &b) {if (a < b) a = b; return a;}

template<class T>
T& cmin(T &a, const T &b) {if (a > b) a = b; return a;}


//区间修改
template<class T, class S>
struct Segment {
    int n;
    vector<T> tree;
    vector<S> lazy;

    Segment() {}
    Segment(int n) {init(n);}
    Segment(vector<T> &a) : n(a.size() - 1), tree((n + 1) << 2), lazy((n + 1) << 2) {
        build(1, 1, n, a);
    }
    void init(int n) {
        this->n = n;
        tree.resize((n + 1) << 2);
        lazy.resize((n + 1) << 2);
    }
    void pushup(int now){
        tree[now] = tree[now << 1] + tree[now << 1 | 1];
    }
    void build(int now, int left, int right, vector<T> &a){       //[l , r]
        if(left == right){
            tree[now] = T(a[left]);
            return ;
        }
        int mid = (left + right) >> 1;
        build(now << 1, left, mid, a);
        build(now << 1 | 1, mid + 1, right, a);
        pushup(now);
    }
    void push(int now, const S &x){
        lazy[now].push(x);
        tree[now].push(x);
    }
    void pushdown(int now){
        push(now << 1, lazy[now]);
        push(now << 1 | 1, lazy[now]);
        lazy[now] = S();
    }
    void modify(int now, int l, int r, int al, int ar, const S &x) {   //[l , r]
        if(al > r || ar < l){
            return;
        }
        if(al <= l && ar >= r){
            push(now, x);
            return;
        }
        pushdown(now);
        int mid = (l + r) >> 1 ;
        modify(now << 1, l, mid, al, ar, x);
        modify(now << 1 | 1, mid + 1, r, al, ar, x);
        pushup(now);
    }
    void modify(int al, int ar, const S &x){
        modify(1, 1, n, al, ar, x);
    }
	void modify(int now, int l, int r, int pos, const T &x) {   //[l , r]
        if (l == r) {
			tree[now] = x;
			return;
		}
        pushdown(now);
        int mid = (l + r) >> 1 ;
        if (pos <= mid) modify(now << 1, l, mid, pos, x);
        else modify(now << 1 | 1, mid + 1, r, pos, x);
        pushup(now);
    }
    void modify(int pos, const T &x){
        modify(1, 1, n, pos, x);
    }
    T ask(int now, int l, int r, int al, int ar) {
        if(al > r || ar < l){
            return T();
        }
        if(al <= l && ar >= r){
            return tree[now];
        }
        pushdown(now);
        int mid = (l + r) >> 1 ;
        return ask(now << 1, l, mid, al, ar) + ask(now << 1 | 1, mid + 1, r, al, ar);
    }
    T ask(int al, int ar) {
        return ask(1, 1, n, al, ar);
    }
    template<class F>
    int ask_first(int now, int l, int r, const F &f) {
        if (l == r) {
            return l;
        }
        pushdown(now);
        int mid = (l + r) >> 1 ;
        if (f(tree[now << 1])) {
            return ask_first(now << 1, l, mid, f);
        } else {
            return ask_first(now << 1 | 1, mid + 1, r, f);
        }
    }
    template<class F>
    int ask_first(const F &f) {
        if (!f(tree[1])) return 0;
        return ask_first(1, 1, n, f);
    }
    template<class F>
    int ask_last(int now, int l, int r, const F &f) {
        if (l == r) {
            return l;
        }
        pushdown(now);
        int mid = (l + r) >> 1 ;
        if (f(tree[now << 1 | 1])) {
            return ask_last(now << 1 | 1, mid + 1, r, f);
        } else {
            return ask_last(now << 1, l, mid, f);
        }
    }
    template<class F>
    int ask_last(const F &f) {
        if (!f(tree[1])) return 0;
        return ask_last(1, 1, n, f);
    }
	template<class F>
    int ask_one(int now, int l, int r, int al, int ar, const F &f) {
		if (l == r) {
			return f(tree[now]) ? l : 0;
		}
        pushdown(now);
        int mid = (l + r) >> 1 ;
        if (al <= l && r <= ar) {
			// cout << l << " " << r << " " << al << " " << ar << "\n";
			if (f(tree[now << 1])) return ask_one(now << 1, l, mid, al, ar, f);
			else if (f(tree[now << 1 | 1])) return ask_one(now << 1 | 1, mid + 1, r, al, ar, f);
			return 0;
		}
		int res = 0;
        if (al <= mid) res = ask_one(now << 1, l, mid, al, ar, f);
        if (res != 0) return res;
        return ask_one(now << 1 | 1, mid + 1, r, al, ar, f);
    }
    template<class F>
    int ask_one(int al, int ar, const F &f) {
        // if (!f(tree[1])) return 0;
        return ask_one(1, 1, n, al, ar, f);
    }
};

struct Info1 {
	ll x;
	Info1() : x(LONG_LONG_MAX) {}
	Info1(ll x) : x(x) {}

	void push(const Info1 &a) {
		x &= a.x;
	}
	friend Info1 operator + (const Info1 &a, const Info1 &b) {
		return a.x & b.x;
	}
};

struct Info2 {
	ll x, y, sz;
	Info2() : x(0), y(0), sz(1) {}
	Info2(ll x, ll y, ll sz) : x(x), y(y), sz(sz) {}

	void push(const Info1 &a) {
		if (sz == 1) {
			x |= LONG_LONG_MAX ^ a.x;
		} else {
			y |= (LONG_LONG_MAX ^ a.x);
			x &= a.x;
		}
	}
	friend Info2 operator + (const Info2 &a, const Info2 &b) {
		ll x = a.x ^ b.x;
		ll y = (a.y | b.y) | (a.x & b.x);
		x = x ^ (x & y);
		// cout << "l : " << bitset<4>(a.x) << " " << bitset<4>(a.y) << "\n";
		// cout << "r : " << bitset<4>(b.x) << " " << bitset<4>(b.y) << "\n";
		// cout << bitset<4>(x) << " " << bitset<4>(y) << "\n";
		return {x, y, a.sz + b.sz};
	}
};



void solve() {
    int n, q;
    cin >> n >> q;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
	Segment<Info1, Info1> t1(n);
	Segment<Info2, Info1> t2(n);
	for (int i = 1; i <= n; ++i) {
		t1.modify(i, a[i]);
		Info2 tmp;
		tmp.push(a[i]);
		t2.modify(i, tmp);
	}
	while(q--) {
		int op, l, r;
		ll x;
		cin >> op >> l;
		if (op == 1) {
			cin >> r >> x;
			t1.modify(l, r, x);
			t2.modify(l, r, x);
		} else if (op == 2) {
			cin >> x;
			t1.modify(l, x);
			Info2 tmp;
			tmp.push(x);
			// cout << x << " " << bitset<4>(tmp.x) << "\n";
			t2.modify(l, tmp);
		} else {
			cin >> r;
			auto [ox, oy, sz] = t2.ask(l, r);
			// cout << bitset<4>(ox) << " " << bitset<4>(oy) << "\n";
			if (ox == 0) {
				cout << t1.ask(l, r).x << "\n";
				continue;
			}
			int pos = __lg(ox);
			int id = t1.ask_one(l, r, [&](const Info1 &info) {
				return !(info.x >> pos & 1);
			});
			// cout << t1.ask(id, id).x << "\n";
			// ll la = t1.ask(l, id - 1).x, ra = t1.ask(id + 1, r).x;
			// cout << id << " " << pos << " " << la << " " << ra << "\n";
			cout << (t1.ask(l, id - 1).x & t1.ask(id + 1, r).x) << "\n";
		}
	}
	
}

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	int t = 1;
	// cin >> t;
	for (int i = 0; i < t; ++i) {
		solve();
	}
	return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3556kb

input:

output:

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 3840kb

input:

10 10
6760061359215711796 1568091718842717482 1568091718842717482 1568091718842717482 5232472783634052627 8795942500783873690 1568091718842717482 1568091718842717482 1568091718842717482 1568091718842717482
1 3 5 7587422031989082829
3 6 10
1 7 8 5197616143400216932
2 4 2518604563805514908
2 2 4533959...

output:

1568091718842717482
35184908959744
176025477579040
8795942500783873690

result:

ok 4 lines

Test #3:

score: 0

Accepted

time: 1ms

memory: 3788kb

input:

100 100
4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 625967318191814868 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072360993 4263579105072...

output:

576531121047601152
1
576460752303423488
4263579105072360993
1306043896232411137
4263579105072360993
576531121047601152
633397148123136
0
1153488865559840256
1152922054496880128
1730020640668059136
3533641810948498945
67108864
1730020640668059136
0
633397148123136
1729382296723653632
0
17300206406680...

result:

ok 78 lines

Test #4:

score: 0

Accepted

time: 1ms

memory: 3744kb

input:

1000 1000
3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3368486440884437410 3639580211161047627 3368486440884437410 3368486440884437410 3368486440...

output:

3368486440884437410
3368486440884437410
3368486440884437410
2251799981457408
0
0
3368486440884437410
0
3326828075601101216
592509842556584322
0
0
0
0
0
0
37154696925806592
0
0
0
3368486440884437410
0
0
3368486440884437410
0
578998425140330496
0
0
134217728
0
3368486440884437410
2306405959167115264
0...

result:

ok 732 lines

Test #5:

score: 0

Accepted

time: 122ms

memory: 22840kb

input:

100000 100000
4364025563773184234 7745126251050571359 5111681002836044963 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7745126251050571359 7222555899134537718 7745126251050571359 686495...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4613942216556019776
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 75105 lines

Test #6:

score: 0

Accepted

time: 1846ms

memory: 198512kb

input:

1000000 1000000
5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485203341817263234 5485...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8796093022208
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
576460754450907136
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 749866 lines

Test #7:

score: 0

Accepted

time: 1850ms

memory: 198424kb

input:

1000000 1000000
6478641409915854014 6478641409915854014 6478641409915854014 6478641409915854014 6478641409915854014 6478641409915854014 6478641409915854014 6478641409915854014 6478641409915854014 6478641409915854014 6478641409915854014 815888006180307319 6478641409915854014 6478641409915854014 37784...

output:

result:

ok 749822 lines

Test #8:

score: 0

Accepted

time: 1859ms

memory: 198536kb

input:

1000000 1000000
8129239286682760854 3981028880940170401 2535635990161413927 8316479514668652599 5147316903112543089 4630570098268037408 8505388156841465368 2203883581249948495 581610100009626881 5079268521394939 1476469952815397946 4914699404295060276 4440084747042452220 2702894635900623841 90540586...

output:

result:

ok 749812 lines

Test #9:

score: 0

Accepted

time: 1836ms

memory: 198632kb

input:

1000000 1000000
7320373167365396487 7320373167365396487 937526916087788458 7320373167365396487 7320373167365396487 7320373167365396487 6758767667984378025 7320373167365396487 7320373167365396487 7320373167365396487 5687396935769483606 1467370155631201061 3556475128226340387 2212274051825085385 77978...

output:

result:

ok 748638 lines

Test #10:

score: 0

Accepted

time: 0ms

memory: 3552kb

input:

2 2
3937866409909043622 2873041425983999763
2 2 3645842096674595914
2 1 5018240021376355677

output:

result:

ok 0 lines

Test #11:

score: 0

Accepted

time: 1835ms

memory: 198760kb

input:

1000000 1000000
4900813446099088166 4900813446099088166 4900813446099088166 4900813446099088166 4900813446099088166 4900813446099088166 4900813446099088166 4900813446099088166 4900813446099088166 4900813446099088166 4900813446099088166 4900813446099088166 4900813446099088166 4900813446099088166 4900...

output:

4900813446099088166
4899930503817200418
4900813446099088166
4899916948900413730
4899916948900413730
4899930503817200418
4899930503817200418
4899930503817200418
4899930503817200418
4900813446099088166
288230380446679040
288230380446679040
4899930503817200418
4899930503817200418
0
768
768
288230724044...

result:

ok 748697 lines

Test #12:

score: 0

Accepted

time: 1824ms

memory: 198324kb

input:

1000000 1000000
4896682234503638342 4896682234503638342 4896682234503638342 4896682234503638342 4896682234503638342 4896682234503638342 4896682234503638342 4896682234503638342 4896682234503638342 4896682234503638342 4896682234503638342 4896682234503638342 4896682234503638342 4896682234503638342 4896...

output:

4896682234503638342
4896682234503638342
4896682234503638342
82333682484117506
4896682234503638342
82333682484117506
9150188513918978
9150188513918978
4896682234503638342
4896682234503638342
9150188513918978
4896682234503638342
9150188513918978
4896682234503638342
4896682234503638342
9150188513918978...

result:

ok 748737 lines

Test #13:

score: 0

Accepted

time: 1823ms

memory: 198500kb

input:

1000000 1000000
5828086749355423563 5828086749355423563 5828086749355423563 5828086749355423563 5828086749355423563 5828086749355423563 5828086749355423563 5828086749355423563 5828086749355423563 5828086749355423563 5828086749355423563 5828086749355423563 5828086749355423563 5828086749355423563 5828...

output:

5828086749355423563
8192
0
0
1152921504793493761
0
0
0
134217728
5828086749355423563
4647719230811407937
0
0
0
0
4647719230811407937
4611686018427396096
0
0
4415226380288
0
0
0
0
4665729214006427657
0
0
4665729213955833856
0
4665733612138661120
0
0
4611686018429485056
4666015104295802624
0
0
0
0
0
4...

result:

ok 749804 lines

Test #14:

score: 0

Accepted

time: 1791ms

memory: 198504kb

input:

1000000 1000000
1970703737173261435 1970703737173261435 1970703737173261435 1970703737173261435 1970703737173261435 1970703737173261435 1970703737173261435 1970703737173261435 1970703737173261435 1970703737173261435 1970703737173261435 1970703737173261435 1970703737173261435 1970703737173261435 1970...

output:

18014398510006272
1970703737173261435
1970703737173261435
18014398510006272
1170935903116331008
1170935903116331008
1242993501449496576
72057598332903424
72127962782629888
72057594037927936
72057598333165568
70405251923968
0
0
0
0
0
0
0
673367418922088530
72127962782892032
18014398509481984
0
704052...

result:

ok 749806 lines

Test #15:

score: 0

Accepted

time: 1820ms

memory: 198728kb

input:

1000000 1000000
1268538845505400998 1268538845505400998 1268538845505400998 1268538845505400998 1268538845505400998 1268538845505400998 1268538845505400998 1268538845505400998 1268538845505400998 1268538845505400998 1268538845505400998 1268538845505400998 1268538845505400998 1268538845505400998 1268...

output:

1191203210145169410
0
0
0
0
0
0
0
8589934592
705069918064678
704786953404416
0
0
1268538845505400998
1268538845505400998
4503633987117056
8589934592
0
633318697730048
2251804108783616
0
0
0
0
4503599627374592
0
0
0
0
704791248371712
1099511627776
0
0
0
1268538845505400998
0
0
633318731153408
1268538...

result:

ok 749818 lines

Test #16:

score: 0

Accepted

time: 1814ms

memory: 198540kb

input:

1000000 1000000
8796374617094329340 8796374617094329340 8796374617094329340 8796374617094329340 8796374617094329340 8796374617094329340 8796374617094329340 8796374617094329340 8796374617094329340 8796374617094329340 8796374617094329340 8796374617094329340 8796374617094329340 8796374617094329340 8796...

output:

0
0
0
0
0
0
0
0
0
0
4612249037637189632
0
0
0
0
0
0
144115189706063880
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
8219350795484238412
0
0
0
536870912
0
0
0
0
0
0
8214847195317895748
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
144115188092633600
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 749921 lines

Test #17:

score: 0

Accepted

time: 1825ms

memory: 198436kb

input:

1000000 1000000
1639525139600828208 1639525139600828208 1639525139600828208 1639525139600828208 1639525139600828208 1639525139600828208 1639525139600828208 1639525139600828208 1639525139600828208 1639525139600828208 1639525139600828208 1639525139600828208 1639525139600828208 1639525139600828208 1639...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
324259173170675712
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
288231492843216896
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
144115188075864064
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0...

result:

ok 749798 lines

Test #18:

score: 0

Accepted

time: 1752ms

memory: 198752kb

input:

1000000 1000000
504297928904866451 504297928904866451 504297928904866451 504297928904866451 504297928904866451 504297928904866451 504297928904866451 504297928904866451 504297928904866451 504297928904866451 504297928904866451 504297928904866451 504297928904866451 504297928904866451 504297928904866451...

output:

504297928904866451
504297928904866451
504297928904866451
504297928904866451
504297928904866451
504297928904866451
504297928904866451
504297928904866451
504297928904866451
504297928904866451
292733989738811392
504297928904866451
504297928904866451
504297928904866451
504297928904866451
504297928904866...

result:

ok 332866 lines

Test #19:

score: -100

Time Limit Exceeded

input:

1000000 1000000
2984855923226151208 2984855923226151208 2984855923226151208 2984855923226151208 2984855923226151208 2984855923226151208 2984855923226151208 2984855923226151208 2984855923226151208 2984855923226151208 2984855923226151208 2984855923226151208 2984855923226151208 2984855923226151208 2984...

output:

2984855923226151208