# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
27792 | 2017-07-14T06:17:12 Z | TAMREF | Palembang Bridges (APIO15_bridge) | C++11 | 173 ms | 12180 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int mx=1e5+5; ll Q[mx], R[mx], M[mx], C[mx<<1]; ll ans; int K,N,U; struct BIT{ ll a[mx<<1]; BIT(){ for(int i=0;i<mx<<1;i++) a[i]=0; } ll s(int i){ ll f=0; for(int j=i;j;j-=j&-j) f+=a[j]; return f; } void u(int i,ll v){ for(int j=i;j<mx<<1;j+=j&-j) a[j]+=v; } }; void input(){ scanf("%d %d",&K,&N); char s,t; for(int i=1;i<=N;i++){ getchar(); scanf("%c %d %c %d",&s,&Q[i],&t,&R[i]); if(s==t){ ans+=llabs(Q[i]-R[i]); --i,--N; } else{ ++ans; if(s=='B') swap(Q[i],R[i]); M[i]=Q[i]+R[i]; C[2*i-1]=Q[i]; C[2*i]=R[i]; } } sort(C+1,C+2*N+1); U=unique(C+1,C+2*N+1)-C; for(int i=1;i<=N;i++) Q[i]=lower_bound(C+1,C+U,Q[i])-C, R[i]=lower_bound(C+1,C+U,R[i])-C; } struct solver1{ BIT x,y,cx,cy; ll tx,ty; ll pro(int t){ int cxs=cx.s(t),cys=cy.s(t); ll xs=x.s(t), ys=y.s(t); return (C[t]*cxs-xs)+((tx-xs)-C[t]*(N-cxs)) +(C[t]*cys-ys)+((ty-ys)-C[t]*(N-cys)); } void solve(){ for(int i=1;i<=N;i++){ x.u(Q[i],C[Q[i]]); y.u(R[i],C[R[i]]); cx.u(Q[i],1); cy.u(R[i],1); } tx=x.s(U-1), ty=y.s(U-1); int p=1,q,r,s=U-1; while(p<s){ q=p+(s-p)/3, r=s-(s-p)/3; if(pro(q)<=pro(r)) s=r-1; else p=q+1; } printf("%lld\n",ans+pro(p)); } } S1; int main(){ input(); if(K==1) S1.solve(); else return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 12180 KB | Output is correct |
2 | Correct | 3 ms | 12180 KB | Output is correct |
3 | Correct | 3 ms | 12180 KB | Output is correct |
4 | Correct | 0 ms | 12180 KB | Output is correct |
5 | Correct | 0 ms | 12180 KB | Output is correct |
6 | Correct | 0 ms | 12180 KB | Output is correct |
7 | Correct | 3 ms | 12180 KB | Output is correct |
8 | Correct | 0 ms | 12180 KB | Output is correct |
9 | Correct | 3 ms | 12180 KB | Output is correct |
10 | Correct | 0 ms | 12180 KB | Output is correct |
11 | Correct | 0 ms | 12180 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 12180 KB | Output is correct |
2 | Correct | 0 ms | 12180 KB | Output is correct |
3 | Correct | 0 ms | 12180 KB | Output is correct |
4 | Correct | 3 ms | 12180 KB | Output is correct |
5 | Correct | 0 ms | 12180 KB | Output is correct |
6 | Correct | 0 ms | 12180 KB | Output is correct |
7 | Correct | 3 ms | 12180 KB | Output is correct |
8 | Correct | 0 ms | 12180 KB | Output is correct |
9 | Correct | 0 ms | 12180 KB | Output is correct |
10 | Correct | 0 ms | 12180 KB | Output is correct |
11 | Correct | 0 ms | 12180 KB | Output is correct |
12 | Correct | 46 ms | 12180 KB | Output is correct |
13 | Correct | 173 ms | 12180 KB | Output is correct |
14 | Correct | 79 ms | 12180 KB | Output is correct |
15 | Correct | 69 ms | 12180 KB | Output is correct |
16 | Correct | 69 ms | 12180 KB | Output is correct |
17 | Correct | 73 ms | 12180 KB | Output is correct |
18 | Correct | 69 ms | 12180 KB | Output is correct |
19 | Correct | 146 ms | 12180 KB | Output is correct |
20 | Correct | 59 ms | 12180 KB | Output is correct |
21 | Correct | 73 ms | 12180 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 12180 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 12180 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 12180 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |