제출 #128484

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
128484	2019-07-11 03:02:04	qkxwsm	새 집 (APIO18_new_home)	C++14	100 / 100	2288 ms	66636 KiB

new_home

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 <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
 
const int mxN=3e5, mxC=1e8;
int n, k, q, x[mxN+2], ts[2*mxN+1], e2i, st[2*(2*mxN+1)], ans[mxN];
vector<array<int, 2>> es1[mxN];
array<int, 3> qs[mxN];
array<int, 4> es2[4*mxN];
 
struct scmp {
  inline bool operator()(const int &a, const int &b) const {
    return x[a]==x[b]?a<b:x[a]<x[b];
  }
};
map<int, int, scmp> smp;
 
inline void solve() {
  for(int i=0; i<k; ++i) {
    smp[n+1]=0;
    for(auto a : es1[i]) {
      auto it1=smp.upper_bound(a[1]), it2=it1--;
      es2[e2i++]={(x[it1->fi]+x[it2->fi]+1)/2, x[it2->fi], it2->se, a[0]};
      it2->se=a[0];
      if(it1->fi==a[1]) {
        it2=it1--;
        es2[e2i++]={(x[it1->fi]+x[a[1]]+1)/2, x[a[1]], it2->se, a[0]};
        smp.erase(it2);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 23 / 23
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20