QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#879018 | #9731. Fuzzy Ranking | frankly6# | WA | 8ms | 9816kb | C++17 | 2.8kb | 2025-02-01 19:48:27 | 2025-02-01 19:48:28 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
#include<queue>
#define int long long
using namespace std;
typedef vector<int> vi;
const int MX=200020;
int T, N, K, Q;
int fa[MX], bel[MX], col[MX], num[MX], now[MX], ans[MX];
int read()
{
int r=0, f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
return r*f;
}
int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}
void merge(int x, int y)
{
x=find(x); y=find(y);
if(x==y) return;
if(x>y) swap(x,y);
fa[y]=x;
}
struct node
{
int u, rk;
bool operator < (const node &a)const{
return rk<a.rk;
}
};
priority_queue<node> q;
signed main()
{
// freopen("testdata.in","r",stdin);
T=read();
while(T--)
{
N=read(); K=read(); Q=read();
vector<vi> sc(N+10,vi(K+10));
for(int i=1;i<=N;i++) fa[i]=i;
for(int i=1;i<=K;i++)
{
while(!q.empty()) q.pop();
for(int j=1;j<=N;j++)
{
sc[i][j]=read();
int r=sc[i][j];
if(i==1) bel[r]=j;
else
{
while(!q.empty())
{
auto [id,rk]=q.top();
if(find(bel[r])<rk) merge(r,id), q.pop();
else break;
}
q.push({r,find(bel[r])});
}
}
}
for(int i=1;i<=N;i++)
col[i]=find(bel[sc[1][i]]);
// cout << "col:"; for(int i=1;i<=N;i++) cout << col[i] << " "; cout << '\n';
for(int i=1;i<=N;i++) num[i]=now[i]=0;
for(int i=1,pre=0;i<=N;i++)
{
pre++;
now[i]=pre;
if(col[i+1]!=col[i]) num[col[i]]=pre, pre=0;
}
for(int i=1;i<=N;i++)
{
ans[i]=ans[i-1];
if(now[i]==num[col[i]]) ans[i]+=num[col[i]]*(num[col[i]]-1)/2;
}
int bef=0;
while(Q--)
{
int id=read(), l=read(), r=read();
id=(id+bef)%K+1;
l=(l+bef)%N+1;
r=(r+bef)%N+1;
int len=r-l+1;
if(col[r]==col[l]) bef=len*(len-1)/2;
else
{
int cnum=num[col[l-1]], c2=num[col[r]];
int len=cnum-now[l-1], l2=now[r];
if(now[l-1]==cnum&&now[r]==c2) bef=ans[r]-ans[l-1];
else if(now[r]==c2) bef=ans[r]-ans[l-1]+len*(len-1)/2;
else if(now[l-1]==cnum) bef=ans[r]-ans[l-1]+l2*(l2-1)/2;
else bef=ans[r]-ans[l-1]+l2*(l2-1)/2+len*(len-1)/2;
}
cout << bef << '\n';
}
}
return (0-0);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9812kb
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
Wrong Answer
time: 8ms
memory: 9816kb
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 ...
output:
15 3 1 0 36 10 3 4 6 0 1 1 10 1 15 3 10 28 0 6 1 6 28 0 0 10 10 6 6 15 0 3 15 15 36 6 21 1 6 1 3 21 -1 28 28 15 28 11 6 4 7 -1 0 0 0 2 -1 16 21 9 0 1 28 -5 2 0 6 2 0 15 6 0 0 3 0 10 0 45 0 10 3 6 28 28 0 21 28 1 10 6 0 0 6 4 1 4 28 10 0 6 0 0 0 0 0 0 0 0 0 0 3 21 0 28 3 0 7 3 1 1 0 0 0 0 0 0 0 0 0 0...
result:
wrong answer 1st lines differ - expected: '1', found: '15'