QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#751266 | #9731. Fuzzy Ranking | 552Hz# | WA | 0ms | 3864kb | C++17 | 4.4kb | 2024-11-15 17:47:31 | 2024-11-15 17:47:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cout<<#x<<": "<<x<<endl
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
using ll=long long;
using ull=unsigned long long;
#define int long long
const int N=2e5+10;
void solve(){
int n,k,q;
cin>>n>>k>>q;
vector<vector<int>> a(k+10,vector<int>(n+10));
vector<vector<int>> id(k+10,vector<int>(n+10));
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
id[i][a[i][j]]=j;
}
}
vector<vector<ll>> pre(k+10,vector<ll>(n+10)),suf(k+10,vector<ll>(n+10));
// if(k<n){
// vector<vector<bitset<N>>> all(k+2,vector<bitset<N>>(n+2)),all2(k+2,vector<bitset<N>>(n+2));
// for(int i=1;i<=k;i++){
// for(int j=n;j>=1;j--){
// all[i][j]|=all[i][j+1];
// all[i][j][a[i][j]]=1;
// }
// for(int j=1;j<=n;j++){
// all2[i][j]|=all2[i][j-1];
// all2[i][j][a[i][j]]=1;
// }
// }
// for(int i=1;i<=k;i++){
// bitset<N> cur;
// for(int j=1;j<=n;j++){
// int ans=0;
// int cv=a[i][j];
// bitset<N> now;
// for(int jj=1;jj<=k;jj++){
// now|=all[jj][id[jj][cv]];
// }
// now&=cur;
// ans=now.count();
// pre[i][j]=ans;
// cur[cv]=1;
// }
// bitset<N> cur2;
// for(int j=n;j>=1;j--){
// int ans=0;
// int cv=a[i][j];
// bitset<N> now;
// for(int jj=1;jj<=k;jj++){
// now|=all2[jj][id[jj][cv]];
// }
// now&=cur2;
// ans=now.count();
// suf[i][j]=ans;
// cur2[cv]=1;
// }
// }
// for(int i=1;i<=k;i++){
// for(int j=1;j<=n;j++){
// suf[i][j]+=suf[i][j-1];
// }
// }
// for(int i=1;i<=k;i++){
// for(int j=n;j>=0;j--){
// pre[i][j]+=pre[i][j+1];
// }
// }
// ll v0=0;
// while(q--){
// int id,l,r;
// cin>>id>>l>>r;
// id=(id+v0)%k+1;
// l=(l+v0)%n+1;
// r=(r+v0)%n+1;
// ll ans=pre[id][0];
// ans-=pre[id][r+1];
// ans-=suf[id][l-1];
// v0=ans;
// cout<<v0<<endl;
// }
// }
// else{
vector<vector<int>> small(n+10,vector<int>(n+10));
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
for(int jj=j+1;jj<=n;jj++){
small[a[i][j]][a[i][jj]]=1;
}
}
}
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
int ans=0;
for(int jj=1;jj<j;jj++){
ans+=small[a[i][j]][a[i][jj]];
}
pre[i][j]=ans;
}
for(int j=n;j>=1;j--){
int ans=0;
for(int jj=n;jj>j;jj--){
ans+=small[a[i][jj]][a[i][j]];
}
suf[i][j]=ans;
}
}
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++){
suf[i][j]+=suf[i][j-1];
}
}
for(int i=1;i<=k;i++){
for(int j=n;j>=0;j--){
pre[i][j]+=pre[i][j+1];
}
}
ll v0=0;
// while(q--){
// int id,l,r;
// cin>>id>>l>>r;
// id=(id+v0)%k+1;
// l=(l+v0)%n+1;
// r=(r+v0)%n+1;
// ll ans=pre[id][0];
// ans-=pre[id][r+1];
// ans-=suf[id][l-1];
// v0=ans;
// cout<<v0<<endl;
// }
// }
}
signed main(){
ios::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
int t;
cin>>t;
while(t--){
solve();
}
}
/*
贡献法
正难则反
数小状压
关系连边
拆位
广义单调性
最长转最短
*/
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3864kb
input:
2 5 2 2 1 2 3 4 5 5 4 3 2 1 1 0 2 1 2 1 5 3 3 1 2 3 4 5 1 3 2 4 5 1 2 3 5 4 0 0 2 0 2 3 1 0 3
output:
result:
wrong answer 1st lines differ - expected: '3', found: ''