oj.uz

Submission #156155

# Submission time Handle Problem Language Result Execution time Memory
156155 2019-10-03T19:25:33 Z wildturtle Arranging Shoes (IOI19_shoes) C++14
0 / 100
 99 ms 76636 KB 
#include "shoes.h"
long long a,b,c,d,i,e,f,g,n,m,k,l,ans,idx,tree[800005],fix[800005],A[800005],B[800005],le,ri;
std::vector <long long> L[800005],R[800005];
void upd(long long node,long long tl,long long tr,long long pos){
	if(tl==tr) { tree[node]=1; return; }
	long long mid=(tl+tr)/2;
	if(pos<=mid) upd(node*2,tl,mid,pos);
	else upd(node*2+1,mid+1,tr,pos);
	tree[node]=tree[node*2]+tree[node*2+1];
}
long long get(long long node,long long tl,long long tr){
	if(ri<tl || tr<le) return 0;
	if(tr<=ri && le<=tl) return tree[node];
	long long mid=(tr+tl)/2;
	long long x=get(node*2,tl,mid);
	long long y=get(node*2+1,mid+1,tr);
	return x+y;
}
long long count_swaps(std::vector<int> s) {
           n=s.size();
           for(long long i=0;i<n;i++) {
                      if(s[i]<0) {
                                 L[-s[i]].push_back(i);
                      }
                      else {
                                 R[s[i]].push_back(i);
                      }
           }
           for(long long i=0;i<n;i++) {
                      if(fix[i]==0) {
                                 if(s[i]<0) {
                                            idx=L[-s[i]][A[-s[i]]];
                                            ri=idx;
                                            le=i;
                                            ans+=(ri-le-1-get(1,0,n-1));
                                            A[-s[i]]++;
                                            B[-s[i]]++;
                                            fix[idx]++;
                                            upd(1,0,n-1,idx);
                                 }
                                 else {
                                            idx=R[s[i]][B[s[i]]];   
                                            ri=idx;
                                            le=i;
                                            ans+=(ri-le-get(1,0,n-1));
                                            A[s[i]]++;
                                            B[s[i]]++;
                                            fix[idx]++;
                                            upd(1,0,n-1,idx);
                                 }
                      }
           }
           return ans;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 76536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 76536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 76536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 76636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 76536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 99 ms 76536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -