oj.uz

Submission #905903

# Submission time Handle Problem Language Result Execution time Memory
905903 2024-01-13T06:59:49 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 155176 KB 
#include <bits/stdc++.h>  
using namespace std;
/*
#pragma GCC optimize("Ofast") 
#pragma comment(linker, "/stack:200000000") 
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" ) 
#pragma GCC optimize("unroll-loops") 
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer") 
#pragma GCC optimize("vpt") 
#pragma GCC optimize("rename-registers") 
#pragma GCC optimize("move-loop-invariants") 
#pragma GCC optimize("unswitch-loops") 
#pragma GCC optimize("function-sections") 
#pragma GCC optimize("data-sections") 
#pragma GCC optimize("branch-target-load-optimize") 
#pragma GCC optimize("branch-target-load-optimize2") 
#pragma GCC optimize("btr-bb-exclusive") 
#pragma GCC optimize("inline") 
#pragma GCC optimize("-fgcse") 
#pragma GCC optimize("-fgcse-lm") 
#pragma GCC optimize("-fipa-sra") 
#pragma GCC optimize("-ftree-pre") 
#pragma GCC optimize("-ftree-vrp") 
#pragma GCC optimize("-fpeephole2") 
#pragma GCC optimize("-ffast-math") 
#pragma GCC optimize("-fsched-spec") 
#pragma GCC optimize("-falign-jumps") 
#pragma GCC optimize("-falign-loops") 
#pragma GCC optimize("-falign-labels") 
#pragma GCC optimize("-fdevirtualize") 
#pragma GCC optimize("-fcaller-saves") 
#pragma GCC optimize("-fcrossjumping") 
#pragma GCC optimize("-fthread-jumps") 
#pragma GCC optimize("-freorder-blocks") 
#pragma GCC optimize("-fschedule-insns") 
#pragma GCC optimize("inline-functions") 
#pragma GCC optimize("-ftree-tail-merge") 
#pragma GCC optimize("-fschedule-insns2") 
#pragma GCC optimize("-fstrict-aliasing") 
#pragma GCC optimize("-falign-functions") 
#pragma GCC optimize("-fcse-follow-jumps") 
#pragma GCC optimize("-fsched-interblock") 
#pragma GCC optimize("-fpartial-inlining") 
#pragma GCC optimize("no-stack-protector") 
#pragma GCC optimize("-freorder-functions") 
#pragma GCC optimize("-findirect-inlining") 
#pragma GCC optimize("-fhoist-adjacent-loads") 
#pragma GCC optimize("-frerun-cse-after-loop") 
#pragma GCC optimize("inline-small-functions") 
#pragma GCC optimize("-finline-small-functions") 
#pragma GCC optimize("-ftree-switch-conversion") 
#pragma GCC optimize("-foptimize-sibling-calls") 
#pragma GCC optimize("-fexpensive-optimizations") 
#pragma GCC optimize("inline-functions-called-once") 
#pragma GCC optimize("-fdelete-null-pointer-checks")
*/
#define ll long long 
#define all(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define f first
#define s second
#define ld long double
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define pb push_back
#define popcount __builtin_popcount
#define endl '\n'
const long double Eps = 1e-12; 
const int max1 = 2e9*1.4; 
const int min1 = -1e9 *1.4;
const ll mod1 = 1000000007;
const ll mod2 = 2000000011;
const ll mod3 = 3000000017;
const ll mod = 998244353;
const int N = 1e6 + 100;
const int B = 4e6 + 100;
const ll INF = 3e18 + 100;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll binpow(ll x,ll y,ll md) {
    if(y == 0) return 1;        
    if(y == 1) return x;
    if(y % 2 == 0) {
        ll now = binpow(x,y/2,md);
        return (1ll*now*now) % md;
    }
    else {
        ll now = binpow(x,y/2,md);
        return (1ll*((1ll*now*now) % md)*x) % md;
    }
}
/*
for(int l = 0;l < logn - 1;l++) {
    for(int i = 0;i + (2 << l)  <= n;i++) {
        sp[l + 1][i] = merge(sp[l][i],sp[l][i + (1 << l)]);
    }
}   
int rmq(int l,int r) {  
    int t = log2(r - l);
    return merge(sp[t][l],sp[t][r - (1 << t)]);
} 
*/ 
int n,q;
int a[N];
long long tree[B];
int tree2[B];
void update2(int ind,int tl,int tr,int v,int x) {
    if(tl == tr) {
        tree2[v] = max(tree2[v],x);
        return;
    }
    int middle = (tl + tr)/2;
    if(middle >= ind) {
        update2(ind,tl,middle,v + v,x);
    }
    else {
        update2(ind,middle + 1,tr,v + v + 1,x);
    }
    tree2[v] = max(tree2[v + v],tree2[v + v + 1]);
}
void build(int tl,int tr,int v) {
    if(tl == tr) {
        tree2[v] = 0;
        return;
    }
    int middle = (tl + tr)/2;
    build(tl,middle,v + v);
    build(middle + 1,tr,v + v + 1);
    tree2[v] = max(tree2[v + v],tree2[v + v + 1]);
}
int getind(int l,int r,int tl,int tr,int v) {
    if(l > r) return 0;
    if(l > tr || tl > r) return 0;
    if(l <= tl&&tr <= r) return tree2[v];
    int middle = (tl + tr)/2;
    return max(getind(l,r,tl,middle,v + v),getind(l,r,middle + 1,tr,v + v + 1));
}
void update(int ind,int x,int tl,int tr,int v) {
    if(tl == tr) {
        tree[v] = max(tree[v],x*1ll);
        return;
    }
    int middle = (tl + tr)/2;
    if(middle >= ind) update(ind,x,tl,middle,v + v);
    else update(ind,x,middle + 1,tr,v + v + 1);
    tree[v] = max(tree[v + v],tree[v + v + 1]);
}   
long long get(int l,int r,int tl,int tr,int v) {
    if(l > tr || tl > r) return 0ll;
    if(l <= tl&&tr <= r) return tree[v];
    int middle = (tl + tr)/2;
    return max(get(l,r,tl,middle,v + v),get(l,r,middle + 1,tr,v + v + 1));
}
signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i = 1;i <= n;i++) cin >> a[i];
    pair <int,pair <int,pair <long long,int> > > p[q + 1]; 
    for(int i = 1;i <= q;i++) cin >> p[i].s.f >> p[i].f >> p[i].s.s.f;
    for(int i = 1;i <= q;i++) p[i].s.s.s = i;
    sort(p + 1,p + q + 1);
    int it = 1;
    int ans[q + 1] = {};
    map <int,int> fnd;
    int temp = 1;
    set <int> s;
    for(int i = 1;i <= n;i++) s.insert(a[i]);
    for(auto x:s) {
        fnd[x] = temp;
        temp++;
    }
    for(int i = 1;i <= q;i++) {
        int r = p[i].f;
        while(it <= r) {
            int ind = getind(fnd[a[it]] + 1,temp,1,temp,1);
            update2(fnd[a[it]],1,temp,1,it);
            if(ind != 0) {
                update(ind,a[ind] + a[it],1,n,1);
            } 
            it++;   
        }
        int l = p[i].s.f;
        long long s = p[i].s.s.f;
        int ind = p[i].s.s.s;
        ans[ind] = (s >= get(l,r,1,n,1));
    }
    for(int i = 1;i <= q;i++) cout << ans[i] << endl;
}

            /*
                                    Lxner & WENARO 
                                         Лед
            -------------------------------------------------------------------
            Вс-все твои слёзы просто превращаю в лёд (В лёд)
            Я спрячу сердце, его никто не найдёт
            Не-не-не-не-не вижу смысла кончить этот эпизод
            Я-я-я вижу выход, но не могу найти вход (—Ход-ход-ход-ход-ход, вход)
      
            Все твои слёзы просто превращаю в лёд
            Я-я-я спрячу сердце, его никто не найдёт (Не найдёт)
            Не вижу смысла кончить этот эпизод (Лё-ё-ёд)
            Я вижу выход, но не могу найти вход (И-и)
            Все твои слёзы просто превращаю в лё-лё-лёд
            Я спрячу сердце, его никто не найдёт (Я-я)
            Не вижу смысла кончить этот эпизод
            Я вижу выход, но не могу найти вход
      
            Мно-мно-много говоришь — пустые слова (—Ва-ва-ва)
            Самый одинокий парень я — навсегда
            Ка-ка-как бы ни хотел, но ты одна нужна
            Боль и слёзы, да, бывает, иногда (Лёд, лёд)
      
            Все твои слёзы просто превращаю в лё-лё-лёд
            Я спрячу сердце, его никто не найдёт (А-а-а-а-а)
            Бывает больно, но я знаю всё пройдёт (Всё пройдёт)
            Я вижу выход, но не могу найти вход (А-а)
            Все твои слёзы просто превращаю в лё-лё-лёд
            Я спрячу сердце, его никто не найдёт (Лё-лё-лё-лё-лёд)
            Бывает больно, но я знаю всё пройдёт (Всё пройдёт)
            Я вижу выход, но не могу найти вход (—Ход-ход-ход-ход, вход)
      
            И не растопишь, и не сможешь забыть (За-а-а-а—)
            Где-то без меня нашла новую жизнь
            Тебя так манит этот холодный мир
            И-и-и-и-и ты как айсберг, ведь я снова разбит
            It's so hard, это сложно
            О-о-она застыла в ожидании солнца-а-а-а
            Но я не думаю что сможет согреть
            Её ледяную душу, остаётся лишь смотреть (А, а, а-а-а-а)
      
            Все твои слёзы просто превращаю в лёд
            Я-я-я спрячу сердце, его никто не найдёт (Не найдёт)
            Не вижу смысла кончить этот эпизод (—З-з-з-од)
            Я вижу выход, но не могу найти вход (И-и)
            Все твои слёзы просто превращаю в лё-лё-лёд
            Я-я спрячу сердце, его никто не найдёт
            Не вижу смысла кончить этот эпизод
            Я вижу выход, но не могу найти вход
            Твои слёзы просто-просто пре— в лёд
            Я-я-я-я прячу сердце, его-его не найдёт (Не найд—, не най—)
            Не вижу смысла кончить-кончить эпизод (А-а-а-а, а-а-а-а)
            Я вижу выход, но не—, но не— найти вход
      
            (—Ход-ход-ход-ход-ход, вход) Все твои слёзы просто превращаю в лёд
            Я-я-я-я спрячу сердце, его никто не найдёт (Не найдёт)
            Не вижу смысла кончить этот эпизод (—З-з-з-од)
            Я вижу выход, но не могу-гу най— вход
            
            */

Compilation message

sortbooks.cpp:69:21: warning: overflow in conversion from 'double' to 'int' changes value from '2.8e+9' to '2147483647' [-Woverflow]
   69 | const int max1 = 2e9*1.4;
      |                  ~~~^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 2 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 2 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 6 ms 3164 KB Output is correct
13 Correct 6 ms 3164 KB Output is correct
14 Correct 7 ms 3160 KB Output is correct
15 Correct 7 ms 3164 KB Output is correct
16 Correct 8 ms 3160 KB Output is correct
17 Correct 7 ms 2908 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 155176 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 9392 KB Output is correct
2 Correct 96 ms 9488 KB Output is correct
3 Correct 83 ms 6388 KB Output is correct
4 Correct 73 ms 6224 KB Output is correct
5 Correct 73 ms 6132 KB Output is correct
6 Correct 67 ms 6152 KB Output is correct
7 Correct 76 ms 6480 KB Output is correct
8 Correct 65 ms 6096 KB Output is correct
9 Correct 35 ms 6228 KB Output is correct
10 Correct 71 ms 6064 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 2 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 6 ms 3164 KB Output is correct
13 Correct 6 ms 3164 KB Output is correct
14 Correct 7 ms 3160 KB Output is correct
15 Correct 7 ms 3164 KB Output is correct
16 Correct 8 ms 3160 KB Output is correct
17 Correct 7 ms 2908 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct
19 Correct 626 ms 37816 KB Output is correct
20 Correct 543 ms 37828 KB Output is correct
21 Correct 547 ms 37952 KB Output is correct
22 Correct 593 ms 38048 KB Output is correct
23 Correct 516 ms 37860 KB Output is correct
24 Correct 280 ms 32720 KB Output is correct
25 Correct 275 ms 32820 KB Output is correct
26 Correct 312 ms 32596 KB Output is correct
27 Correct 290 ms 32596 KB Output is correct
28 Correct 306 ms 32820 KB Output is correct
29 Correct 304 ms 32848 KB Output is correct
30 Correct 293 ms 32736 KB Output is correct
31 Correct 301 ms 32836 KB Output is correct
32 Correct 311 ms 32964 KB Output is correct
33 Correct 297 ms 32712 KB Output is correct
34 Correct 294 ms 34644 KB Output is correct
35 Correct 278 ms 34872 KB Output is correct
36 Correct 284 ms 34864 KB Output is correct
37 Correct 292 ms 34640 KB Output is correct
38 Correct 273 ms 34640 KB Output is correct
39 Correct 321 ms 34232 KB Output is correct
40 Correct 193 ms 25140 KB Output is correct
41 Correct 126 ms 11856 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 2 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 6 ms 3164 KB Output is correct
13 Correct 6 ms 3164 KB Output is correct
14 Correct 7 ms 3160 KB Output is correct
15 Correct 7 ms 3164 KB Output is correct
16 Correct 8 ms 3160 KB Output is correct
17 Correct 7 ms 2908 KB Output is correct
18 Correct 4 ms 2652 KB Output is correct
19 Execution timed out 3036 ms 155176 KB Time limit exceeded
20 Halted 0 ms 0 KB -