QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #575707 | #21566. 四维偏序 | jeffqi | Compile Error | / | / | C++17 | 2.9kb | 2024-09-19 16:22:26 | 2024-09-19 16:22:27 |
Judging History
answer
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define ll long long
#define all(v) v.begin(),v.end()
#define sz(v) ((ll)v.size())
#define V vector
#define vi V<int>
#define vll V<ll>
#define eb emplace_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define A array
#define pb push_back
#define mset multiset
#define gpumap __gnu_pbds::gp_hash_table
#define ccumap __gnu_pbds::cc_hash_table
#define ui unsigned int
#define ull unsigned ll
#define i128 __int128
#define cerr if (test) cerr
#define freopen if (test) freopen
#define whtest if (test)
using namespace std;
const int test = 0;
namespace jhsy {
template<class F,class Cmp>
void solve(span<int> vec,int d,vi &cnt,int m,F &&f,Cmp &&cmp) {
if (sz(vec) == 1) {
return;
}
if (d == m) {
return f(vec,cnt);
}
const int n = sz(vec),mid = n/2;
span<int> vl(vec.begin(),vec.begin()+mid);
vi vr(vec.begin()+mid,vec.end());
solve(vl,d,cnt,m,f,cmp);
solve(vr,d,cnt,m,f,cmp);
vi tmp(n);
ranges::merge(vl,vr,tmp.begin(),cmp(d));
for (int i = 0; i < n; i++) {
vec[i] = tmp[i];
}
for (auto x:vr) {
cnt[x]++;
}
solve(tmp,d+1,cnt,m,f,cmp);
for (auto x:vr) {
cnt[x]--;
}
}
template<class F,class Cmp>
void solve(int n,int m,F &&f,Cmp &&cmp) {
if (!n || !m) {
return;
}
vi vec(n),cnt(n);
iota(all(vec),0);
sort(all(vec),cmp(0));
solve(vec,1,cnt,m,f,cmp);
}
struct BIT {
int n; vll a;
BIT(int n):n(n),a(n,0) {}
int lbt(int x) {
return 1<<__builtin_ctz(x);
}
void upd(int x,ll k) {
for (int i = x+1; i <= n; i += lbt(i)) {
a[i-1] += k;
}
}
ll qry(int x) {
ll k = 0;
for (int i = x; i > 0; i -= lbt(i)) {
k += a[i-1];
}
return k;
}
ll qry(int l,int r) {
return qry(r)-qry(l);
}
int kth(int k) {
if (!n) {
return 0;
}
int x = 0;
for (int i = 1<<__lg(n); i; i /= 2) {
if (x+i <= n && k >= a[x+i-1]) {
x += i; k -= a[x-1];
}
}
return x;
}
};
const int D = 4;
void main() {
int n;
cin >> n;
V<A<int,D>> a(n);
for (auto &p:a) {
for (auto &x:p) {
cin >> x;
}
}
ll ans = 0; BIT bit(n);
solve(n,D-1,[&](const span<int> vec,const vi &cnt) {
for (auto x:vec) {
if (cnt[x] == D-2) {
ans += bit.qry(a[x][D-1]);
}
if (!cnt[x]) {
bit.upd(a[x][D-1],1);
}
}
for (auto x:vec) {
if (!cnt[x]) {
bit.upd(a[x][D-1],-1);
}
}
},[&](int d) {
return [&,d](int x,int y) {
return a[x][d] < a[y][d];
};
});
cout << ans << '\n';
}
}
int main() {
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(20);
// jhsy::init();
int T = 1;
// cin >> T;
while (T--) {
jhsy::main();
}
return 0;
}
Details
answer.code:32:14: error: variable or field ‘solve’ declared void
32 | void solve(span<int> vec,int d,vi &cnt,int m,F &&f,Cmp &&cmp) {
| ^~~~~
answer.code:32:20: error: ‘span’ was not declared in this scope
32 | void solve(span<int> vec,int d,vi &cnt,int m,F &&f,Cmp &&cmp) {
| ^~~~
answer.code:32:20: note: ‘std::span’ is only available from C++20 onwards
answer.code:32:25: error: expected primary-expression before ‘int’
32 | void solve(span<int> vec,int d,vi &cnt,int m,F &&f,Cmp &&cmp) {
| ^~~
answer.code:32:34: error: expected primary-expression before ‘int’
32 | void solve(span<int> vec,int d,vi &cnt,int m,F &&f,Cmp &&cmp) {
| ^~~
answer.code:32:43: error: expected primary-expression before ‘&’ token
32 | void solve(span<int> vec,int d,vi &cnt,int m,F &&f,Cmp &&cmp) {
| ^
answer.code:32:44: error: ‘cnt’ was not declared in this scope; did you mean ‘int’?
32 | void solve(span<int> vec,int d,vi &cnt,int m,F &&f,Cmp &&cmp) {
| ^~~
| int
answer.code:32:48: error: expected primary-expression before ‘int’
32 | void solve(span<int> vec,int d,vi &cnt,int m,F &&f,Cmp &&cmp) {
| ^~~
answer.code:32:56: error: expected primary-expression before ‘&&’ token
32 | void solve(span<int> vec,int d,vi &cnt,int m,F &&f,Cmp &&cmp) {
| ^~
answer.code:32:58: error: ‘f’ was not declared in this scope
32 | void solve(span<int> vec,int d,vi &cnt,int m,F &&f,Cmp &&cmp) {
| ^
answer.code:32:64: error: expected primary-expression before ‘&&’ token
32 | void solve(span<int> vec,int d,vi &cnt,int m,F &&f,Cmp &&cmp) {
| ^~
answer.code:32:66: error: ‘cmp’ was not declared in this scope; did you mean ‘Cmp’?
32 | void solve(span<int> vec,int d,vi &cnt,int m,F &&f,Cmp &&cmp) {
| ^~~
| Cmp
answer.code: In function ‘void jhsy::main()’:
answer.code:112:39: error: ‘span’ does not name a type
112 | solve(n,D-1,[&](const span<int> vec,const vi &cnt) {
| ^~~~
answer.code:126:19: error: expected identifier before ‘[’ token
126 | },[&](int d) {
| ^
answer.code:126:21: error: expected primary-expression before ‘]’ token
126 | },[&](int d) {
| ^
answer.code:126:29: error: expected ‘)’ before ‘{’ token
126 | },[&](int d) {
| ^~
| )
answer.code:112:32: note: to match this ‘(’
112 | solve(n,D-1,[&](const span<int> vec,const vi &cnt) {
| ^
answer.code: In lambda function:
answer.code:127:35: error: ‘d’ was not declared in this scope
127 | return [&,d](int x,int y) {
| ^
answer.code: In function ‘void jhsy::main()’:
answer.code:112:22: error: no matching function for call to ‘solve(int&, int, jhsy::main()::<lambda(...)>)’
112 | solve(n,D-1,[&](const span<int> vec,const vi &cnt) {
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
113 | for (auto x:vec) {
| ~~~~~~~~~~~~~~~~~~
114 | if (cnt[x] == D-2) {
| ~~~~~~~~~~~~~~~~~~~~
115 | ans += bit.qry(a[x][D-1]);
| ~~~~~~~~~~~~~~~~~~~~~~~~~~
116 | }
| ~
117 | if (!cnt[x]) {
| ~~~~~~~~~~~~~~
118 | bit.upd(a[x][D-1],1);
| ~~~~~~~~~~~~~~~~~~~~~
119 | }
| ~
120 | }
| ~
121 | for (auto x:vec) {
| ~~~~~~~~~~~~~~~~~~
122 | if (!cnt[x]) {
| ~~~~~~~~~~~~~~
123 | bit.upd(a[x][D-1],-1);
| ~~~~~~~~~~~~~~~...