QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#537945 | #9155. 集合 | MetalPower# | 100 ✓ | 621ms | 62852kb | C++14 | 2.9kb | 2024-08-30 19:58:31 | 2024-08-30 19:58:31 |
Judging History
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