QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#489644#9155. 集合Fracture-Dream100 ✓675ms115972kbC++142.8kb2024-07-24 22:12:192024-07-24 22:12:19

Judging History

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

  • [2024-07-24 22:12:19]
  • 评测
  • 测评结果:100
  • 用时:675ms
  • 内存:115972kb
  • [2024-07-24 22:12:19]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 6e5 + 5;
int n , m , q , rnk[MAXN] , suma[MAXN] , sumb[MAXN] , posr[MAXN] , all;
int a[MAXN][3] , b[MAXN][3];
unordered_map<int , int> mpA , mpB;
mt19937 rd(time(0));
uniform_int_distribution<int>val(-1e9 , 1e9);
int f(int id) {return rnk[id] * id;}
void adda(int pos , int id , int tp) {
    if (suma[pos]) {
        all -= abs(mpA[suma[pos]] - mpB[suma[pos]]);
        mpA[suma[pos]] --;
        all += abs(mpA[suma[pos]] - mpB[suma[pos]]);
    }
    suma[pos] += f(id) * tp;
    if (suma[pos]) {
        all -= abs(mpA[suma[pos]] - mpB[suma[pos]]);
        mpA[suma[pos]] ++;
        all += abs(mpA[suma[pos]] - mpB[suma[pos]]);
    }
}
void addb(int pos , int id , int tp) {
    if (sumb[pos]) {
        all -= abs(mpA[sumb[pos]] - mpB[sumb[pos]]);
        mpB[sumb[pos]] --;
        all += abs(mpA[sumb[pos]] - mpB[sumb[pos]]);
    }
    sumb[pos] += f(id) * tp;
    if (sumb[pos]) {
        all -= abs(mpA[sumb[pos]] - mpB[sumb[pos]]);
        mpB[sumb[pos]] ++;
        all += abs(mpA[sumb[pos]] - mpB[sumb[pos]]);
    }
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr) , cout.tie(nullptr);
	cin >> n >> m >> q;
	for (int i = 1 ; i <= n ; i ++) rnk[i] = val(rd) * val(rd);
	for (int i = 1 ; i <= n ; i ++) cin >> a[i][0] >> a[i][1] >> a[i][2];
	for (int i = 1 ; i <= n ; i ++) cin >> b[i][0] >> b[i][1] >> b[i][2];
	int l = 1 , r = 1;
	for (int i = 0 ; i < 3 ; i ++) adda(a[1][i] , 1 , 1);
	for (int i = 0 ; i < 3 ; i ++) addb(b[1][i] , 1 , 1);
	while(l <= n) {
		if (!all) {
			posr[l] = r;
			if (r == n) {
                for (int i = 0 ; i < 3 ; i ++) adda(a[l][i] , l , -1);
                for (int i = 0 ; i < 3 ; i ++) addb(b[l][i] , l , -1);
                l ++;
            } else {
                r ++;
                for (int i = 0 ; i < 3 ; i ++) adda(a[r][i] , r , 1);
                for (int i = 0 ; i < 3 ; i ++) addb(b[r][i] , r , 1);
            }
		} else {
            if (l == r) {
                for (int i = 0 ; i < 3 ; i ++) adda(a[l][i] , l , -1);
                for (int i = 0 ; i < 3 ; i ++) addb(b[l][i] , l , -1);
                l ++ , r ++;
                for (int i = 0 ; i < 3 ; i ++) adda(a[l][i] , l , 1);
                for (int i = 0 ; i < 3 ; i ++) addb(b[l][i] , l , 1);              
            } else {
                for (int i = 0 ; i < 3 ; i ++) adda(a[l][i] , l , -1);
                for (int i = 0 ; i < 3 ; i ++) addb(b[l][i] , l , -1);                
                l ++;
            }
		}
	}
    for (int i = 1 ; i <= n ; i ++) posr[i] = max(posr[i - 1] , posr[i]);
	while(q --) {
		int l , r;
		cin >> l >> r;
		if (posr[l] >= r) cout << "Yes" << '\n';
		else cout << "No" << '\n'; 
	}
	return 0;
} 

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 21ms
memory: 10160kb

Pretest #10:

score: 5
Accepted
time: 14ms
memory: 10132kb

Pretest #11:

score: 5
Accepted
time: 566ms
memory: 115972kb

Pretest #12:

score: 5
Accepted
time: 538ms
memory: 109720kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 108ms
memory: 10676kb

Pretest #16:

score: 5
Accepted
time: 113ms
memory: 10728kb

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 37ms
memory: 23352kb

Pretest #19:

score: 5
Accepted
time: 675ms
memory: 110256kb

Pretest #20:

score: 5
Accepted
time: 661ms
memory: 105692kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 23ms
memory: 10148kb

Test #10:

score: 5
Accepted
time: 21ms
memory: 9908kb

Test #11:

score: 5
Accepted
time: 516ms
memory: 106392kb

Test #12:

score: 5
Accepted
time: 532ms
memory: 107380kb

Test #13:

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

Test #14:

score: 5
Accepted
time: 4ms
memory: 12948kb

Test #15:

score: 5
Accepted
time: 112ms
memory: 10640kb

Test #16:

score: 5
Accepted
time: 105ms
memory: 10628kb

Test #17:

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

Test #18:

score: 5
Accepted
time: 32ms
memory: 19652kb

Test #19:

score: 5
Accepted
time: 632ms
memory: 110764kb

Test #20:

score: 5
Accepted
time: 659ms
memory: 112784kb

Extra Test:

score: 0
Extra Test Passed