Task: | Concentric Tubes |
Sender: | Niilo |
Submission time: | 2024-11-27 17:42:49 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
#7 | ACCEPTED | 0.00 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
#14 | ACCEPTED | 0.00 s | details |
#15 | ACCEPTED | 0.00 s | details |
#16 | ACCEPTED | 0.01 s | details |
#17 | ACCEPTED | 0.03 s | details |
#18 | ACCEPTED | 0.31 s | details |
Code
#include <iostream>#include <cmath>#include <vector>#include <cassert>#include <algorithm>#include <map>using namespace std;#define rep(i, a, b) for(int i=a;i<(b);++i)#define all(x) begin(x),end(x)#define sz(x) int((x).size())using ll = long long;using pii = pair<int,int>;using vi = vector<int>;const int N = 1<<18;using seg_type = pii;seg_type S[N*2];void add(int i, seg_type x) {i |= N;S[i] = max(S[i], x);for (i /= 2; i >= 1; i /= 2) {S[i] = max(S[i*2], S[i*2+1]);}}seg_type Sget(int a, int b) {a |= N; b |= N;seg_type s = {0,0};while (a <= b) {if (a % 2 == 1) {s = max(s, S[a]);++a;} if (b % 2 == 0) {s = max(s, S[b]);--b;}a /= 2; b /= 2;}return s;}int W[N*2];tuple<int,int,int> R[N];int ANS[N];int main() {int n;cin >> n;rep(i,0,n) {int r;cin >> r;R[i] = {0,r,0};W[i] = r;}rep(i,0,n) {int r;cin >> r;R[i] = {r,get<1>(R[i]),i+1};W[n+i] = r;}// indexsort(W,W+n*2);map<int,int> M;int w = 0;int index = 0;rep(i,0,n*2) {if (W[i] != w) {w = W[i];M[w] = index++;}}// sortrep(i,0,n) {auto [r2,r1,ind] = R[i];R[i] = {-M[r2], -M[r1], ind};}sort(R,R+n);// segrep(i,0,n) {auto [r2,r1,rInd] = R[i];auto [val,ind] = Sget(-r2,n*2);ANS[rInd] = ind;add(-r1, {val+1,rInd});}// ansauto [val,ind] = Sget(0,n*2);cout << val << '\n';do {cout << ind << ' ';ind = ANS[ind];} while (ind);cout << '\n';}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
1 5 10 |
correct output |
---|
1 1 |
user output |
---|
1 1 |
Test 2
Verdict: ACCEPTED
input |
---|
2 2 3 5 10 |
correct output |
---|
1 1 |
user output |
---|
1 2 |
Test 3
Verdict: ACCEPTED
input |
---|
3 6 2 3 9 4 8 |
correct output |
---|
2 2 1 |
user output |
---|
2 2 1 |
Test 4
Verdict: ACCEPTED
input |
---|
4 9 9 6 3 10 10 8 7 |
correct output |
---|
2 4 1 |
user output |
---|
2 4 2 |
Test 5
Verdict: ACCEPTED
input |
---|
5 3 2 9 6 2 5 10 10 9 3 |
correct output |
---|
4 5 1 4 3 |
user output |
---|
4 5 1 4 3 |
Test 6
Verdict: ACCEPTED
input |
---|
6 2 5 2 3 7 1 10 10 4 10 9 2 |
correct output |
---|
3 6 3 5 |
user output |
---|
3 6 3 5 |
Test 7
Verdict: ACCEPTED
input |
---|
7 2 4 4 4 4 6 2 6 10 9 6 5 10 8 |
correct output |
---|
2 5 6 |
user output |
---|
2 5 6 |
Test 8
Verdict: ACCEPTED
input |
---|
8 4 2 2 4 5 5 5 5 9 5 10 7 9 8 6 9 |
correct output |
---|
2 2 7 |
user output |
---|
2 2 8 |
Test 9
Verdict: ACCEPTED
input |
---|
9 1 3 6 5 3 2 2 2 3 2 5 9 6 6 4 3 4 5 |
correct output |
---|
5 1 7 2 4 3 |
user output |
---|
5 1 7 9 4 3 |
Test 10
Verdict: ACCEPTED
input |
---|
10 4 2 2 6 7 4 3 4 2 3 8 4 3 8 8 5 8 9 6 7 |
correct output |
---|
3 3 6 4 |
user output |
---|
3 3 10 5 |
Test 11
Verdict: ACCEPTED
input |
---|
10 3 2 1 7 5 3 8 2 5 2 6 4 2 10 6 9 10 10 9 10 |
correct output |
---|
4 3 2 5 4 |
user output |
---|
4 3 2 5 7 |
Test 12
Verdict: ACCEPTED
input |
---|
10 3 2 8 4 2 1 6 7 2 4 10 6 10 9 4 2 10 8 3 5 |
correct output |
---|
5 6 9 10 8 3 |
user output |
---|
5 6 9 10 8 3 |
Test 13
Verdict: ACCEPTED
input |
---|
10 6 7 4 7 8 9 7 3 8 5 8 8 7 9 9 10 10 5 10 8 |
correct output |
---|
4 8 1 5 6 |
user output |
---|
4 8 10 5 6 |
Test 14
Verdict: ACCEPTED
input |
---|
10 6 3 6 4 4 4 2 3 3 3 10 10 8 7 9 5 6 6 4 8 |
correct output |
---|
3 9 6 3 |
user output |
---|
3 9 6 3 |
Test 15
Verdict: ACCEPTED
input |
---|
100 822996947 734489027 192088037 ... |
correct output |
---|
12 91 79 84 15 7 86 24 59 65 61 4... |
user output |
---|
12 91 79 84 15 63 86 24 59 66 61 ... |
Test 16
Verdict: ACCEPTED
input |
---|
1000 111735663 297257984 561742368 ... |
correct output |
---|
32 358 507 775 556 630 679 280 25... |
user output |
---|
32 358 507 775 556 630 679 280 25... Truncated |
Test 17
Verdict: ACCEPTED
input |
---|
10000 316394141 195182398 569713189 ... |
correct output |
---|
112 1134 6761 4604 3840 20 7490 92... |
user output |
---|
112 5555 6761 9624 7611 20 7490 92... Truncated |
Test 18
Verdict: ACCEPTED
input |
---|
100000 457164810 81615942 542726432 3... |
correct output |
---|
363 9442 43192 86004 46207 95417 2... |
user output |
---|
363 60910 43192 86004 98028 40484 ... Truncated |