QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#352364#4425. Cakeucup-team1209#AC ✓4015ms69968kbC++201.4kb2024-03-13 10:29:572024-03-13 10:29:57

Judging History

你现在查看的是最新测评结果

  • [2024-03-13 10:29:57]
  • 评测
  • 测评结果:AC
  • 用时:4015ms
  • 内存:69968kb
  • [2024-03-13 10:29:57]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,x,y) for (int i=(x);i>=(y);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
#define sz 505050

int n;
int a[sz][2],b[sz][2];

int tr[sz];
void add(int x){while (x<=n) tr[x]++,x+=x&-x;}
int query(int x){int res=0;while (x) res+=tr[x],x-=x&-x;return res;}

void work() {
    cin>>n;
    rep(j,0,1) rep(i,1,n) cin>>a[i][j];
    rep(j,0,1) rep(i,1,n) cin>>b[i][j];
    rep(i,1,n) if (i&1) swap(a[i][0],a[i][1]),swap(b[i][0],b[i][1]);
    map<ll,vector<int>>posb;
    rep(i,1,n) {
        ll y=1ll*b[i][0]*int(1e9+7)+b[i][1];
        posb[y].push_back(i);
    }
    static int p[sz];
    drep(i,n,1) {
        ll x=1ll*a[i][0]*int(1e9+7)+a[i][1];
        if (!posb[x].size()) return cout<<"-1\n",void();
        p[i]=posb[x].back(); posb[x].pop_back();
    }
    ll ans=0;
    drep(i,n,1) ans+=query(p[i]),add(p[i]);
    rep(i,1,n) tr[i]=0;
    cout<<ans<<'\n';
}

int main() {
    file();
    ios::sync_with_stdio(false),cin.tie(0);
    int T; cin>>T;
    while (T--) work();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3735ms
memory: 69964kb

input:

4
500000
471518156 319758862 812815356 520822448 129241996 461169933 796713727 608641317 281180101 953966756 749634941 274104949 996181952 88142916 998544672 125597509 991731126 974767231 338911715 674197249 167602044 682799026 226927279 703198907 216742488 8185420 94921423 690039818 859329736 45428...

output:

0
-1
124999750000
62569045381

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 4015ms
memory: 69968kb

input:

4
500000
413978977 447850293 802546055 289227062 321812178 97254226 380555063 167654142 874843339 349071516 10868808 93093321 996630037 33169052 99312773 335065051 278187197 94810404 643530967 947474510 63047182 573006260 8470509 116477506 251504796 899920047 806158195 452300674 859769748 489596554 ...

output:

62623368052
62486676013
62520737719
62506121292

result:

ok 4 lines

Test #3:

score: 0
Accepted
time: 684ms
memory: 4908kb

input:

9082
7
714942297 703160828 709363739 23094554 461254804 159017923 666590460
196100940 70571239 755082029 321718821 55663261 378527017 335969190
321718821 335969190 70571239 755082029 378527017 55663261 714942297
23094554 666590460 703160828 709363739 159017923 461254804 196100940
5
2 1 1 2 1
2 1 2 2...

output:

13
5
0
-1
0
2
10
2
0
5
0
10
15
1
2336
-1
1
-1
-1
4
-1
15
0
9
45
15
3
4
0
11
-1
-1
10
-1
18
10
0
3
1
-1
0
1
0
5
-1
16
-1
-1
-1
15
-1
307294
-1
7
0
0
-1
-1
-1
0
2210
3
1
16
-1
-1
0
-1
0
0
5
5
10
3
0
-1
21
0
7
3
0
32308741
-1
20
-1
0
1
-1
9
6
2249
0
-1
0
55236
2265
1
12
-1
-1
29
0
-1
20
0
2
0
0
1
-1
0
...

result:

ok 9082 lines

Extra Test:

score: 0
Extra Test Passed