Submission #29885875

Source Code Expand

#include<bits/stdc++.h> #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define op(x) ((x&1)?x+1:x-1) #define odd(x) (x&1) #define even(x) (!odd(x)) #define lc(x) (x<<1) #define rc(x) (lc(x)|1) #define lowbit(x) (x&-x) #define mp(x,y) make_pair(x,y) typedef long long ll; typedef unsigned long long ull; typedef double db; using namespace std; const int MAXN=1e5+10,MAXM=1e6+10,LIM=2000; int n,q,a[MAXN],cnt[MAXN],l[MAXM],r[MAXM]; vector<int>occ[MAXN]; int ans[MAXM]; vector<array<int,2>>qry[MAXN]; struct BIT{ int t[MAXN]; void add(int x,int val){ for(;x<=n;x+=lowbit(x))t[x]+=val; } void add(int l,int r,int val){ add(l,val);add(r+1,-val); } int qry(int x){ int ret=0; for(;x;x-=lowbit(x))ret+=t[x]; return ret; } }t; int main(){ ios::sync_with_stdio(false); cin>>n; rep(i,1,n){ cin>>a[i]; cnt[a[i]]++; } cin>>q; rep(i,1,q){ cin>>l[i]>>r[i]; qry[r[i]].push_back({l[i],i}); } rep(i,1,n)occ[i].push_back(0); rep(i,1,n){ int cur=occ[a[i]].size(); occ[a[i]].push_back(i); if(cnt[a[i]]<LIM){ cur-=2; while(cur>=0){ int l=occ[a[i]][cur],r=occ[a[i]][cur+1]; t.add(l+1,r,1); cur-=2; } for(auto p:qry[i]){ ans[p[1]]+=t.qry(p[0]); } } } memset(t.t,0,sizeof t.t); rep(i,1,n){ if(cnt[i]<LIM)continue; rep(j,1,n)if(a[j]==i)t.add(j,n,1); rep(j,1,q){ int s=t.qry(r[j])-t.qry(l[j]-1); ans[j]+=s/2; } rep(j,1,n)if(a[j]==i)t.add(j,n,-1); } rep(i,1,q)cout<<ans[i]<<endl; return 0; }

Submission Info

Submission Time
Task G - Range Pairing Query
User Crying
Language C++ (GCC 9.2.1)
Score 600
Code Size 1827 Byte
Status AC
Exec Time 2094 ms
Memory 40136 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 1
AC × 30
Set Name Test Cases
Sample sample_01.txt
All pair_01.txt, pair_02.txt, pair_03.txt, pair_04.txt, sample_01.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt
Case Name Status Exec Time Memory
pair_01.txt AC 1811 ms 39824 KiB
pair_02.txt AC 1763 ms 38808 KiB
pair_03.txt AC 1745 ms 38712 KiB
pair_04.txt AC 1745 ms 38780 KiB
sample_01.txt AC 8 ms 8572 KiB
test_01.txt AC 7 ms 8580 KiB
test_02.txt AC 1046 ms 23952 KiB
test_03.txt AC 1255 ms 30524 KiB
test_04.txt AC 211 ms 15448 KiB
test_05.txt AC 986 ms 26168 KiB
test_06.txt AC 363 ms 15780 KiB
test_07.txt AC 256 ms 12504 KiB
test_08.txt AC 494 ms 15640 KiB
test_09.txt AC 72 ms 11232 KiB
test_10.txt AC 1577 ms 34096 KiB
test_11.txt AC 1676 ms 39384 KiB
test_12.txt AC 2060 ms 40136 KiB
test_13.txt AC 1778 ms 40084 KiB
test_14.txt AC 1677 ms 39804 KiB
test_15.txt AC 1708 ms 38760 KiB
test_16.txt AC 1723 ms 39584 KiB
test_17.txt AC 2071 ms 40076 KiB
test_18.txt AC 1729 ms 40016 KiB
test_19.txt AC 1680 ms 39892 KiB
test_20.txt AC 1677 ms 38688 KiB
test_21.txt AC 1681 ms 39460 KiB
test_22.txt AC 2054 ms 40028 KiB
test_23.txt AC 1804 ms 39924 KiB
test_24.txt AC 2094 ms 40056 KiB
test_25.txt AC 1650 ms 36652 KiB