oj.uz

답안 #905914

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
905914 2024-01-13T07:07:08 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 153644 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 = 1e9*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 = 2e6 + 1000000;
const int B = 8e6 + 1000000;
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 << 1);
    build(middle + 1,tr,(v << 1) | 1);
    tree2[v] = max(tree2[v << 1],tree2[(v << 1) | 1]);
}
int getind(int l,int r,int tl,int tr,int v) {
    if(l > tr || tl > r) return 0;
    if(l <= tl&&tr <= r) return tree2[v];
    int middle = ((tl + tr) >> 1);
    return max(getind(l,r,tl,middle,v << 1),getind(l,r,middle + 1,tr,(v << 1) | 1));
}
void update(int ind,long long 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) >> 1);
    return max(get(l,r,tl,middle,v << 1),get(l,r,middle + 1,tr,(v << 1) | 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] = {};
    unordered_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:4: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    4 | #pragma comment(linker, "/stack:200000000")
      | 
sortbooks.cpp:7:71: warning: bad option '-fprofile-values' to pragma 'optimize' [-Wpragmas]
    7 | #pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
      |                                                                       ^
sortbooks.cpp:12:41: warning: bad option '-ffunction-sections' to pragma 'optimize' [-Wpragmas]
   12 | #pragma GCC optimize("function-sections")
      |                                         ^
sortbooks.cpp:13:37: warning: bad option '-fdata-sections' to pragma 'optimize' [-Wpragmas]
   13 | #pragma GCC optimize("data-sections")
      |                                     ^
sortbooks.cpp:14:51: warning: bad option '-fbranch-target-load-optimize' to pragma 'optimize' [-Wpragmas]
   14 | #pragma GCC optimize("branch-target-load-optimize")
      |                                                   ^
sortbooks.cpp:15:52: warning: bad option '-fbranch-target-load-optimize2' to pragma 'optimize' [-Wpragmas]
   15 | #pragma GCC optimize("branch-target-load-optimize2")
      |                                                    ^
sortbooks.cpp:16:40: warning: bad option '-fbtr-bb-exclusive' to pragma 'optimize' [-Wpragmas]
   16 | #pragma GCC optimize("btr-bb-exclusive")
      |                                        ^
sortbooks.cpp:77:26: warning: bad option '-fprofile-values' to attribute 'optimize' [-Wattributes]
   77 | ll binpow(ll x,ll y,ll md) {
      |                          ^
sortbooks.cpp:77:26: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:77:26: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:77:26: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:77:26: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:77:26: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:104:47: warning: bad option '-fprofile-values' to attribute 'optimize' [-Wattributes]
  104 | void update2(int ind,int tl,int tr,int v,int x) {
      |                                               ^
sortbooks.cpp:104:47: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:104:47: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:104:47: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:104:47: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:104:47: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:118:31: warning: bad option '-fprofile-values' to attribute 'optimize' [-Wattributes]
  118 | void build(int tl,int tr,int v) {
      |                               ^
sortbooks.cpp:118:31: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:118:31: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:118:31: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:118:31: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:118:31: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:128:43: warning: bad option '-fprofile-values' to attribute 'optimize' [-Wattributes]
  128 | int getind(int l,int r,int tl,int tr,int v) {
      |                                           ^
sortbooks.cpp:128:43: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:128:43: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:128:43: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:128:43: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:128:43: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:134:52: warning: bad option '-fprofile-values' to attribute 'optimize' [-Wattributes]
  134 | void update(int ind,long long x,int tl,int tr,int v) {
      |                                                    ^
sortbooks.cpp:134:52: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:134:52: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:134:52: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:134:52: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:134:52: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:144:46: warning: bad option '-fprofile-values' to attribute 'optimize' [-Wattributes]
  144 | long long get(int l,int r,int tl,int tr,int v) {
      |                                              ^
sortbooks.cpp:144:46: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:144:46: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:144:46: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:144:46: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:144:46: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:150:13: warning: bad option '-fprofile-values' to attribute 'optimize' [-Wattributes]
  150 | signed main() {
      |             ^
sortbooks.cpp:150:13: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:150:13: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:150:13: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:150:13: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:150:13: warning: bad option '-fbtr-bb-exclusive' to attribute 'optimize' [-Wattributes]

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 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 2392 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 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 2392 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2808 KB Output is correct
12 Correct 5 ms 3164 KB Output is correct
13 Correct 6 ms 3220 KB Output is correct
14 Correct 7 ms 3164 KB Output is correct
15 Correct 6 ms 3164 KB Output is correct
16 Correct 5 ms 3164 KB Output is correct
17 Correct 4 ms 2908 KB Output is correct
18 Correct 3 ms 2648 KB Output is correct

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3059 ms 153644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 8376 KB Output is correct
2 Correct 83 ms 8284 KB Output is correct
3 Correct 63 ms 6148 KB Output is correct
4 Correct 80 ms 6112 KB Output is correct
5 Correct 76 ms 6112 KB Output is correct
6 Correct 57 ms 6148 KB Output is correct
7 Correct 60 ms 6152 KB Output is correct
8 Correct 56 ms 6228 KB Output is correct
9 Correct 34 ms 6228 KB Output is correct
10 Correct 52 ms 6052 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 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 2392 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2808 KB Output is correct
12 Correct 5 ms 3164 KB Output is correct
13 Correct 6 ms 3220 KB Output is correct
14 Correct 7 ms 3164 KB Output is correct
15 Correct 6 ms 3164 KB Output is correct
16 Correct 5 ms 3164 KB Output is correct
17 Correct 4 ms 2908 KB Output is correct
18 Correct 3 ms 2648 KB Output is correct
19 Correct 379 ms 34484 KB Output is correct
20 Correct 480 ms 34840 KB Output is correct
21 Correct 439 ms 34548 KB Output is correct
22 Correct 459 ms 34456 KB Output is correct
23 Correct 429 ms 34564 KB Output is correct
24 Correct 225 ms 30328 KB Output is correct
25 Correct 234 ms 30328 KB Output is correct
26 Correct 282 ms 30292 KB Output is correct
27 Correct 275 ms 30328 KB Output is correct
28 Correct 262 ms 30196 KB Output is correct
29 Correct 371 ms 30244 KB Output is correct
30 Correct 337 ms 30316 KB Output is correct
31 Correct 323 ms 30328 KB Output is correct
32 Correct 307 ms 30376 KB Output is correct
33 Correct 277 ms 30588 KB Output is correct
34 Correct 223 ms 30332 KB Output is correct
35 Correct 301 ms 30220 KB Output is correct
36 Correct 240 ms 30332 KB Output is correct
37 Correct 268 ms 30316 KB Output is correct
38 Correct 264 ms 30312 KB Output is correct
39 Correct 224 ms 31612 KB Output is correct
40 Correct 143 ms 22468 KB Output is correct
41 Correct 118 ms 9844 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 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 2392 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 2 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2808 KB Output is correct
12 Correct 5 ms 3164 KB Output is correct
13 Correct 6 ms 3220 KB Output is correct
14 Correct 7 ms 3164 KB Output is correct
15 Correct 6 ms 3164 KB Output is correct
16 Correct 5 ms 3164 KB Output is correct
17 Correct 4 ms 2908 KB Output is correct
18 Correct 3 ms 2648 KB Output is correct
19 Execution timed out 3059 ms 153644 KB Time limit exceeded
20 Halted 0 ms 0 KB -