QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#879024#9731. Fuzzy Rankingfrankly6#WA 9ms11852kbC++172.9kb2025-02-01 19:55:062025-02-01 19:55:06

Judging History

This is the latest submission verdict.

  • [2025-02-01 19:55:06]
  • Judged
  • Verdict: WA
  • Time: 9ms
  • Memory: 11852kb
  • [2025-02-01 19:55:06]
  • Submitted

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 L=r-l+1;
            if(col[r]==col[l]) bef=L*(L-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';
        }
        for(int i=1;i<=N;i++) num[i]=now[i]=ans[i]=col[i]=fa[i]=bel[i]=0;
    }
    return (0-0);
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 11852kb

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: 9ms
memory: 11836kb

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'