Submission #353273

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
3532732021-01-21 07:11:22dolphingarlicAncient Books (IOI17_books)C++14
50 / 100
369 ms127724 KiB
#include "books.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int crit_l, crit_r;
int cmp[1000000], cmp_l[1000000], cmp_r[1000000];
map<pair<int, int>, ll> dp;
void extend(int &l, int &r) {
int ext_l = min(cmp_l[cmp[l]], cmp_l[cmp[r]]);
int ext_r = max(cmp_r[cmp[l]], cmp_r[cmp[r]]);
while (l != ext_l || r != ext_r) {
if (l != ext_l) {
l--;
ext_l = min(ext_l, cmp_l[cmp[l]]);
ext_r = max(ext_r, cmp_r[cmp[l]]);
} else {
r++;
ext_l = min(ext_l, cmp_l[cmp[r]]);
ext_r = max(ext_r, cmp_r[cmp[r]]);
}
}
}
ll compute(int l, int r) {
extend(l, r);
if (dp.count({l, r})) return dp[{l, r}];
if (l == crit_l) return dp[{l, r}] = compute(l, r + 1) + 2;
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...