제출 #44509

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
44509	2018-04-02 17:51:46	faustaadp	Gap (APIO16_gap)	C++17	17.68 / 100	130 ms	2448 KiB

gap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "gap.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll ma,u1,u2,ce,L1,R1,L2,R2,L,R;
priority_queue<pair<ll,pair<ll,ll> > >pq;
long long findGap(int T, int N)
{
  ma=0;
  MinMax(0,(ll)1e18,&L,&R);
  pq.push(mp(R-L,mp(L,R)));
  while(!pq.empty())
  {
    u1=pq.top().se.fi;
    u2=pq.top().se.se;
    pq.pop();
    ce=(u1+u2)/2;
    MinMax(u1,ce,&L1,&R1);
    MinMax(ce+1,u2,&L2,&R2);
    ma=max(ma,L2-R1);
    if(R1-L1>ma)
      pq.push(mp(R1-L1,mp(L1,R1)));
    if(R2-L2>ma)
      pq.push(mp(R2-L2,mp(L2,R2)));
  }
  return ma;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 30
• Subtask 2: 17.6761970257 / 70