Submission #1698409
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))
using ll = long long;
using P = std::tuple<int,int>;
using P3 = std::tuple<int,int,int>;
const int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1}, dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};
const int INF = numeric_limits<int>::max() / 2;
P ps[100100], dp[100100];
int orderOfLeft[100100], orderOfRight[100100];
int mapping[100100], mapping2[100100]; // ps -> oOl, ps -> oOr
// I want to delete this stupid solution ;(
#define sandwich(x) [](auto a, auto b){return (x)(a, b);}
template <typename T>
using F2 = std::function<T(T,T)>;
template <typename T, int N>
struct SegmentTree{
SegmentTree(){
size = 1;
while(size < N){
size <<= 1;
}
unit = 0;
init();
}
void init(){
for(int i=0;i<size;++i){
data[i+size] = unit;
data2[i+size] = i;
}
for(int i=size-1;i>0;--i){
data[i] = unit;
data2[i] = data2[i*2];
}
}
void update(int k, T v){
k += size;
data[k] = v;
while(k > 1){
k >>= 1;
if(data[k*2] > data[k*2+1]){
data[k] = data[k*2];
data2[k] = data2[k*2];
}else{
data[k] = data[k*2+1];
if(data[k*2] == data[k*2+1]){
data2[k] = data2[k*2+1] > N || orderOfLeft[data2[k*2]] < orderOfLeft[data2[k*2+1]] ? data2[k*2] : data2[k*2+1];
}else{
data2[k] = data2[k*2+1];
}
}
}
}
inline tuple<T, int> query(int l, int r){
return _query(l, r, 1, 0, size);
}
tuple<T, int> _query(int a, int b, int k, int l, int r){
if(b <= l || r <= a){return std::make_tuple(unit, -1);}
if(a <= l && r <= b){return std::make_tuple(data[k], data2[k]);}
int mid = (l + r) >> 1;
auto p1 = _query(a, b, 2*k, l, mid),
p2 = _query(a, b, 2*k+1, mid, r );
if(fst(p1) > fst(p2)){
return p1;
}else if(fst(p1) < fst(p2)){
return p2;
}else if(snd(p1) == -1){
return p2;
}else if(snd(p2) == -1){
return p1;
}else if(orderOfLeft[snd(p1)] < orderOfLeft[snd(p2)]){
return p1;
}
return p2;
}
T unit, data[N*4], data2[N*4];
int size;
};
SegmentTree<int, 100100> seg;
int main(){
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int N;
std::cin >> N;
for(int i=1;i<=N;++i){
int a, b;
std::cin >> a >> b;
ps[i] = std::make_tuple(a, b);
}
iota(orderOfLeft + 1, orderOfLeft + 1 + N, 1);
iota(orderOfRight + 1, orderOfRight + 1 + N, 1);
sort(orderOfLeft + 1, orderOfLeft + 1 + N, [&](const int lhs, const int rhs){
return fst(ps[lhs]) <= fst(ps[rhs]);
});
sort(orderOfRight + 1, orderOfRight + 1 + N, [&](const int lhs, const int rhs){
return snd(ps[lhs]) <= snd(ps[rhs]);
});
for(int i=1;i<=N;++i){
mapping[orderOfLeft[i]] = i;
mapping2[orderOfRight[i]] = i;
}
for(int i=N;i>0;--i){
int r;
tie(ignore, r) = ps[orderOfRight[i]];
int first;
{
int lb = N, ub = 0;
while(std::abs(ub - lb) > 1){
int mid = (lb + ub) / 2;
if(fst(ps[orderOfLeft[mid]]) >= r){
lb = mid;
}else{
ub = mid;
}
}
first = fst(ps[orderOfLeft[lb]]) >= r ? lb : N + 1;
}
int max_n, next_idx;
tie(max_n, next_idx) = seg.query(first, N + 1);
next_idx = mapping2[orderOfLeft[next_idx]];
if(max_n == 0){
dp[i] = std::make_tuple(1, -1);
}else{
dp[i] = std::make_tuple(max_n + 1, next_idx);
}
int i_in_oOl = mapping[orderOfRight[i]];
seg.update(i_in_oOl, fst(dp[i]));
}
// int first = 1;
// for(int i=2;i<=N;++i){
// if(fst(dp[i]) == fst(dp[1]) && orderOfRight[i] < orderOfRight[first]){
// first = i;
// }
// }
// vector<int> res;
// while(first != -1){
// res.emplace_back(orderOfRight[first]);
// first = snd(dp[first]);
// }
// std::cout << res.size() << std::endl;
// for(int i=0;i<res.size();++i){
// std::cout << res[i] << " \n"[i + 1 == res.size()];
// }
}
Submission Info
Submission Time |
|
Task |
C - 仕事計画 |
User |
iwashisnake |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
4882 Byte |
Status |
RE |
Exec Time |
124 ms |
Memory |
6016 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 100 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
0.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 3.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
0.txt |
WA |
3 ms |
5888 KB |
1.txt |
WA |
3 ms |
5888 KB |
10.txt |
WA |
3 ms |
5888 KB |
11.txt |
WA |
3 ms |
5888 KB |
12.txt |
RE |
98 ms |
5888 KB |
13.txt |
WA |
3 ms |
5888 KB |
14.txt |
WA |
3 ms |
5888 KB |
15.txt |
RE |
100 ms |
5888 KB |
16.txt |
WA |
3 ms |
5888 KB |
17.txt |
WA |
3 ms |
5888 KB |
18.txt |
RE |
114 ms |
6016 KB |
19.txt |
RE |
124 ms |
6016 KB |
2.txt |
WA |
3 ms |
5888 KB |
20.txt |
WA |
85 ms |
6016 KB |
21.txt |
RE |
113 ms |
6016 KB |
22.txt |
RE |
114 ms |
6016 KB |
23.txt |
WA |
79 ms |
6016 KB |
3.txt |
WA |
3 ms |
5888 KB |
4.txt |
WA |
3 ms |
5888 KB |
5.txt |
WA |
3 ms |
5888 KB |
6.txt |
WA |
3 ms |
5888 KB |
7.txt |
WA |
3 ms |
5888 KB |
8.txt |
WA |
3 ms |
5888 KB |
9.txt |
WA |
3 ms |
5888 KB |
sample1.txt |
WA |
3 ms |
5888 KB |
sample2.txt |
WA |
3 ms |
5888 KB |
sample3.txt |
WA |
3 ms |
5888 KB |