oj.uz

Submission #417672

# Submission time Handle Problem Language Result Execution time Memory
417672 2021-06-04T06:13:46 Z MarcoMeijer Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 2833 ms 104276 KB 
#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
//===================//
//   begin program   //
//===================//
 
const int MX = 1e6+10;
const int N = (1<<20);

int n, m;
int w[MX];
int l[MX], r[MX], k[MX];

// fenwick tree
int ft[MX];
void addFT(int x, int v) {
    for(x++; x>0; x-=x&-x)
        ft[x] = max(ft[x], v);
}
int getFT(int x) {
    int res = 0;
    for(x++; x<MX; x+=x&-x)
        res = max(res,ft[x]);
    return res;
}

// queries
int a[MX];
vi qend[MX];
int ans[MX];

void program() {
    IN(n,m);
    RE1(i,n) IN(w[i]);
    RE(i,m) IN(l[i],r[i],k[i]);

    RE(i,m) qend  [r[i]].pb(i);

    vi stck;
    RE1(i,n) {
        int lowest = stck.empty() ? -1 : a[stck.back()];
        int ed = i;
        while(!stck.empty() && a[stck.back()] <= w[i]) {
            int u = stck.back(); stck.pop_back();
            if(a[u] != lowest && lowest != -1)
                addFT(ed-1,a[u] + lowest);
            ed = u;
            lowest = max(lowest, a[u]);
        }
        stck.pb(ed);
        a[ed] = w[i];
        FOR(j,qend[i]) {
            int res = getFT(l[j]);
            auto it = upper_bound(all(stck),l[j]);
            it--;
            auto it2 = it;
            it2++;
            if(it2 != stck.end())
                res = max(res, a[*it] + a[*it2]);
            ans[j] = res <= k[j];
        }
    }

    RE(i,m) cout<<ans[i]<<endl;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 15 ms 23732 KB Output is correct
3 Correct 15 ms 23820 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 16 ms 23832 KB Output is correct
7 Correct 16 ms 23884 KB Output is correct
8 Correct 16 ms 23800 KB Output is correct
9 Correct 16 ms 23756 KB Output is correct
10 Correct 15 ms 23756 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 15 ms 23732 KB Output is correct
3 Correct 15 ms 23820 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 16 ms 23832 KB Output is correct
7 Correct 16 ms 23884 KB Output is correct
8 Correct 16 ms 23800 KB Output is correct
9 Correct 16 ms 23756 KB Output is correct
10 Correct 15 ms 23756 KB Output is correct
11 Correct 20 ms 23944 KB Output is correct
12 Correct 21 ms 23932 KB Output is correct
13 Correct 21 ms 24012 KB Output is correct
14 Correct 27 ms 24096 KB Output is correct
15 Correct 26 ms 24068 KB Output is correct
16 Correct 25 ms 24012 KB Output is correct
17 Correct 25 ms 23952 KB Output is correct
18 Correct 24 ms 24044 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2771 ms 71132 KB Output is correct
2 Correct 2804 ms 104060 KB Output is correct
3 Correct 2833 ms 103924 KB Output is correct
4 Correct 2817 ms 104276 KB Output is correct
5 Correct 2658 ms 96148 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 28296 KB Output is correct
2 Correct 223 ms 27672 KB Output is correct
3 Correct 223 ms 27364 KB Output is correct
4 Correct 226 ms 27520 KB Output is correct
5 Correct 236 ms 27680 KB Output is correct
6 Correct 215 ms 26512 KB Output is correct
7 Correct 219 ms 26692 KB Output is correct
8 Correct 229 ms 27456 KB Output is correct
9 Correct 203 ms 26088 KB Output is correct
10 Correct 222 ms 27452 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 15 ms 23732 KB Output is correct
3 Correct 15 ms 23820 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 16 ms 23832 KB Output is correct
7 Correct 16 ms 23884 KB Output is correct
8 Correct 16 ms 23800 KB Output is correct
9 Correct 16 ms 23756 KB Output is correct
10 Correct 15 ms 23756 KB Output is correct
11 Correct 20 ms 23944 KB Output is correct
12 Correct 21 ms 23932 KB Output is correct
13 Correct 21 ms 24012 KB Output is correct
14 Correct 27 ms 24096 KB Output is correct
15 Correct 26 ms 24068 KB Output is correct
16 Correct 25 ms 24012 KB Output is correct
17 Correct 25 ms 23952 KB Output is correct
18 Correct 24 ms 24044 KB Output is correct
19 Correct 490 ms 32856 KB Output is correct
20 Correct 488 ms 32936 KB Output is correct
21 Correct 449 ms 31180 KB Output is correct
22 Correct 453 ms 31244 KB Output is correct
23 Correct 456 ms 31240 KB Output is correct
24 Correct 447 ms 29508 KB Output is correct
25 Correct 444 ms 29556 KB Output is correct
26 Correct 452 ms 30148 KB Output is correct
27 Correct 453 ms 30332 KB Output is correct
28 Correct 458 ms 30660 KB Output is correct
29 Correct 480 ms 31304 KB Output is correct
30 Correct 471 ms 31380 KB Output is correct
31 Correct 476 ms 31224 KB Output is correct
32 Correct 484 ms 31376 KB Output is correct
33 Correct 492 ms 31344 KB Output is correct
34 Correct 446 ms 29252 KB Output is correct
35 Correct 442 ms 29236 KB Output is correct
36 Correct 437 ms 29240 KB Output is correct
37 Correct 446 ms 29300 KB Output is correct
38 Correct 450 ms 29232 KB Output is correct
39 Correct 450 ms 31596 KB Output is correct
40 Correct 440 ms 30496 KB Output is correct
41 Correct 455 ms 31080 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Correct 15 ms 23732 KB Output is correct
3 Correct 15 ms 23820 KB Output is correct
4 Correct 15 ms 23808 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 16 ms 23832 KB Output is correct
7 Correct 16 ms 23884 KB Output is correct
8 Correct 16 ms 23800 KB Output is correct
9 Correct 16 ms 23756 KB Output is correct
10 Correct 15 ms 23756 KB Output is correct
11 Correct 20 ms 23944 KB Output is correct
12 Correct 21 ms 23932 KB Output is correct
13 Correct 21 ms 24012 KB Output is correct
14 Correct 27 ms 24096 KB Output is correct
15 Correct 26 ms 24068 KB Output is correct
16 Correct 25 ms 24012 KB Output is correct
17 Correct 25 ms 23952 KB Output is correct
18 Correct 24 ms 24044 KB Output is correct
19 Correct 2771 ms 71132 KB Output is correct
20 Correct 2804 ms 104060 KB Output is correct
21 Correct 2833 ms 103924 KB Output is correct
22 Correct 2817 ms 104276 KB Output is correct
23 Correct 2658 ms 96148 KB Output is correct
24 Correct 232 ms 28296 KB Output is correct
25 Correct 223 ms 27672 KB Output is correct
26 Correct 223 ms 27364 KB Output is correct
27 Correct 226 ms 27520 KB Output is correct
28 Correct 236 ms 27680 KB Output is correct
29 Correct 215 ms 26512 KB Output is correct
30 Correct 219 ms 26692 KB Output is correct
31 Correct 229 ms 27456 KB Output is correct
32 Correct 203 ms 26088 KB Output is correct
33 Correct 222 ms 27452 KB Output is correct
34 Correct 490 ms 32856 KB Output is correct
35 Correct 488 ms 32936 KB Output is correct
36 Correct 449 ms 31180 KB Output is correct
37 Correct 453 ms 31244 KB Output is correct
38 Correct 456 ms 31240 KB Output is correct
39 Correct 447 ms 29508 KB Output is correct
40 Correct 444 ms 29556 KB Output is correct
41 Correct 452 ms 30148 KB Output is correct
42 Correct 453 ms 30332 KB Output is correct
43 Correct 458 ms 30660 KB Output is correct
44 Correct 480 ms 31304 KB Output is correct
45 Correct 471 ms 31380 KB Output is correct
46 Correct 476 ms 31224 KB Output is correct
47 Correct 484 ms 31376 KB Output is correct
48 Correct 492 ms 31344 KB Output is correct
49 Correct 446 ms 29252 KB Output is correct
50 Correct 442 ms 29236 KB Output is correct
51 Correct 437 ms 29240 KB Output is correct
52 Correct 446 ms 29300 KB Output is correct
53 Correct 450 ms 29232 KB Output is correct
54 Correct 450 ms 31596 KB Output is correct
55 Correct 440 ms 30496 KB Output is correct
56 Correct 455 ms 31080 KB Output is correct
57 Correct 2797 ms 103076 KB Output is correct
58 Correct 2794 ms 102972 KB Output is correct
59 Correct 2634 ms 98740 KB Output is correct
60 Correct 2590 ms 98864 KB Output is correct
61 Correct 2553 ms 98804 KB Output is correct
62 Correct 2527 ms 98744 KB Output is correct
63 Correct 2269 ms 83216 KB Output is correct
64 Correct 2221 ms 83408 KB Output is correct
65 Correct 2446 ms 90476 KB Output is correct
66 Correct 2464 ms 90516 KB Output is correct
67 Correct 2426 ms 90752 KB Output is correct
68 Correct 2530 ms 95056 KB Output is correct
69 Correct 2552 ms 95244 KB Output is correct
70 Correct 2537 ms 94460 KB Output is correct
71 Correct 2545 ms 94404 KB Output is correct
72 Correct 2548 ms 94448 KB Output is correct
73 Correct 2189 ms 81268 KB Output is correct
74 Correct 2227 ms 82292 KB Output is correct
75 Correct 2193 ms 81424 KB Output is correct
76 Correct 2188 ms 81264 KB Output is correct
77 Correct 2199 ms 81300 KB Output is correct
78 Correct 2431 ms 89848 KB Output is correct
79 Correct 2219 ms 78124 KB Output is correct
80 Correct 2372 ms 84900 KB Output is correct