QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #751254 | #9731. Fuzzy Ranking | 552Hz# | RE | 0ms | 5468kb | C++17 | 4.3kb | 2024-11-15 17:44:26 | 2024-11-15 17:44:27 |
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+2,vector<int>(n+2));
vector<vector<int>> id(k+2,vector<int>(n+2));
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+2,vector<ll>(n+2)),suf(k+2,vector<ll>(n+2));
// 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+2,vector<int>(n+2));
// 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();
}
}
/*
贡献法
正难则反
数小状压
关系连边
拆位
广义单调性
最长转最短
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5468kb
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:
3 10 1 1 2
result:
ok 5 lines
Test #2:
score: -100
Runtime Error
input:
2000 10 10 10 4 5 3 6 8 9 2 1 7 10 4 5 6 3 8 9 1 2 10 7 5 4 3 6 8 9 1 2 7 10 4 5 6 3 8 9 1 2 7 10 4 5 3 6 8 9 2 1 10 7 4 5 6 3 8 9 1 2 10 7 5 4 6 3 8 9 1 2 7 10 5 4 6 3 8 9 1 2 10 7 4 5 6 3 8 9 2 1 7 10 5 4 3 6 8 9 2 1 10 7 3 1 6 5 7 8 0 2 3 7 9 9 2 1 9 6 1 6 7 2 3 0 0 4 1 8 1 1 8 7 10 10 10 9 10 5 ...