QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#537945#9155. 集合MetalPower#100 ✓621ms62852kbC++142.9kb2024-08-30 19:58:312024-08-30 19:58:31

Judging History

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

  • [2024-08-30 19:58:31]
  • 评测
  • 测评结果:100
  • 用时:621ms
  • 内存:62852kb
  • [2024-08-30 19:58:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#pragma GCC("Ofast")

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

const int MX = 2e5 + 105;
const int MK = 6e5 + 105;

int N, M, Q, A[MX][3][2], to[MX];

struct segtree{
	int st[MX << 1];

	void upd(int p, int v){
		for(p += MX, st[p] = v, p >>= 1; p > 0; p >>= 1) st[p] = min(st[p << 1], st[p << 1|1]);
	}

	int que(int l, int r){
		int res = N + 1;
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1) res = min(res, st[l++]);
			if(r & 1) res = min(res, st[--r]);
		}
		return res;
	}
} S;

struct node{
	int mx; short num;

	node(int x = 0) : mx(x), num(1) {}

	friend node operator + (node a, node b) {
		if(a.mx > b.mx) return a;
		if(a.mx < b.mx) return b;
		node c;
		c.mx = a.mx, c.num = a.num + b.num;
		return c;
	}
};

int inc = 0, sum = M, cnt[MK], hitung[MK];

void chmin(int& a, int b){
	if(b < a) a = b;
}

void add(int a, int b, int c){
	// cout << "Add " << a << " " << b << " " << c << " have inc " << inc << " and sum " << sum << '\n';
	inc++; 
	hitung[cnt[a]]--, hitung[++cnt[a]]++;
	hitung[cnt[b]]--, hitung[++cnt[b]]++;
	hitung[cnt[c]]--, hitung[++cnt[c]]++;
	sum = inc == 0 ? M : hitung[inc];
}

void del(int a, int b, int c){
	// cout << "Del " << a << " " << b << " " << c << " have inc " << inc << " and sum " << sum << '\n';
	inc--; 
	hitung[cnt[a]]--, hitung[--cnt[a]]++;
	hitung[cnt[b]]--, hitung[--cnt[b]]++;
	hitung[cnt[c]]--, hitung[--cnt[c]]++;
	sum = inc == 0 ? M : hitung[inc];
}

void solve(int tp){
	vector<pair<ll, int>> ls;

	for(int i = 1; i <= N; i++){
		for(int mask = 1; mask < 8; mask++){
			ll curr = 0;
			for(int j = 0; j < 3; j++)
				if(mask >> j & 1) curr = curr * M + A[i][j][tp];
			ls.push_back({curr * 4 + __builtin_popcount(mask), i});
		}
	}

	sort(ls.begin(), ls.end());
	sum = M;

	for(int i = 0, j = -1; i < (int) ls.size(); i = ++j){
		for(; j + 1 < (int) ls.size() && ls[j + 1].fi == ls[i].fi; ) j++;

		int num = ls[i].fi % 4;

		// cout << "SEARCH MASK " << num << '\n';
		for(int lf = i, rg = i - 1; lf <= j; lf++){
			for(; rg <= j && sum >= num; rg++){
				if(rg + 1 <= j) add(A[ls[rg + 1].se][0][tp ^ 1], A[ls[rg + 1].se][1][tp ^ 1], A[ls[rg + 1].se][2][tp ^ 1]);
			}

			chmin(to[ls[lf].se], rg <= j ? ls[rg].se : N + 1);
			del(A[ls[lf].se][0][tp ^ 1], A[ls[lf].se][1][tp ^ 1], A[ls[lf].se][2][tp ^ 1]);
		}
		// cout << '\n';
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> M >> Q;

	for(int k = 0; k < 2; k++){
		for(int i = 1; i <= N; i++){
			for(int j = 0; j < 3; j++){
				cin >> A[i][j][k];
				A[i][j][k]--;
			}
		}
	}

	for(int i = 1; i <= N; i++) to[i] = N + 1;

	solve(0);
	solve(1);

	for(int i = 1; i <= N; i++) S.upd(i, to[i]);

	for(int i = 0; i < Q; i++){
		int l, r; cin >> l >> r;
		if(S.que(l, r) > r) cout << "Yes\n";
		else cout << "No\n";
	}
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 1ms
memory: 7728kb

Pretest #2:

score: 5
Accepted
time: 1ms
memory: 7724kb

Pretest #3:

score: 5
Accepted
time: 1ms
memory: 7748kb

Pretest #4:

score: 5
Accepted
time: 0ms
memory: 7720kb

Pretest #5:

score: 5
Accepted
time: 0ms
memory: 9776kb

Pretest #6:

score: 5
Accepted
time: 2ms
memory: 9960kb

Pretest #7:

score: 5
Accepted
time: 0ms
memory: 7652kb

Pretest #8:

score: 5
Accepted
time: 1ms
memory: 7980kb

Pretest #9:

score: 5
Accepted
time: 28ms
memory: 7704kb

Pretest #10:

score: 5
Accepted
time: 24ms
memory: 7708kb

Pretest #11:

score: 5
Accepted
time: 411ms
memory: 60612kb

Pretest #12:

score: 5
Accepted
time: 431ms
memory: 61824kb

Pretest #13:

score: 5
Accepted
time: 0ms
memory: 7848kb

Pretest #14:

score: 5
Accepted
time: 5ms
memory: 8084kb

Pretest #15:

score: 5
Accepted
time: 160ms
memory: 7724kb

Pretest #16:

score: 5
Accepted
time: 160ms
memory: 7816kb

Pretest #17:

score: 5
Accepted
time: 36ms
memory: 15140kb

Pretest #18:

score: 5
Accepted
time: 36ms
memory: 17064kb

Pretest #19:

score: 5
Accepted
time: 604ms
memory: 60292kb

Pretest #20:

score: 5
Accepted
time: 607ms
memory: 62672kb

Final Tests

Test #1:

score: 5
Accepted
time: 0ms
memory: 7608kb

Test #2:

score: 5
Accepted
time: 1ms
memory: 7952kb

Test #3:

score: 5
Accepted
time: 1ms
memory: 7876kb

Test #4:

score: 5
Accepted
time: 1ms
memory: 10000kb

Test #5:

score: 5
Accepted
time: 0ms
memory: 7588kb

Test #6:

score: 5
Accepted
time: 1ms
memory: 7672kb

Test #7:

score: 5
Accepted
time: 2ms
memory: 9836kb

Test #8:

score: 5
Accepted
time: 1ms
memory: 7760kb

Test #9:

score: 5
Accepted
time: 28ms
memory: 7768kb

Test #10:

score: 5
Accepted
time: 28ms
memory: 7708kb

Test #11:

score: 5
Accepted
time: 400ms
memory: 62852kb

Test #12:

score: 5
Accepted
time: 458ms
memory: 61488kb

Test #13:

score: 5
Accepted
time: 5ms
memory: 7776kb

Test #14:

score: 5
Accepted
time: 5ms
memory: 7864kb

Test #15:

score: 5
Accepted
time: 160ms
memory: 8028kb

Test #16:

score: 5
Accepted
time: 165ms
memory: 9840kb

Test #17:

score: 5
Accepted
time: 35ms
memory: 13472kb

Test #18:

score: 5
Accepted
time: 26ms
memory: 16364kb

Test #19:

score: 5
Accepted
time: 615ms
memory: 62240kb

Test #20:

score: 5
Accepted
time: 621ms
memory: 62292kb

Extra Test:

score: 0
Extra Test Passed