oj.uz

답안 #905916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
905916 2024-01-13T07:08:11 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 152820 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,1ll*a[ind] + 1ll*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 2392 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 2392 KB Output is correct
7 Correct 2 ms 2396 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 2392 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 2392 KB Output is correct
7 Correct 2 ms 2396 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 3 ms 2648 KB Output is correct
12 Correct 5 ms 3164 KB Output is correct
13 Correct 5 ms 3164 KB Output is correct
14 Correct 8 ms 3164 KB Output is correct
15 Correct 7 ms 3160 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 2652 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 8576 KB Output is correct
2 Correct 82 ms 8348 KB Output is correct
3 Correct 63 ms 6228 KB Output is correct
4 Correct 63 ms 6224 KB Output is correct
5 Correct 63 ms 6228 KB Output is correct
6 Correct 56 ms 6352 KB Output is correct
7 Correct 57 ms 6224 KB Output is correct
8 Correct 52 ms 6148 KB Output is correct
9 Correct 42 ms 6228 KB Output is correct
10 Correct 51 ms 6248 KB Output is correct

Subtask #5
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 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 2392 KB Output is correct
7 Correct 2 ms 2396 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 3 ms 2648 KB Output is correct
12 Correct 5 ms 3164 KB Output is correct
13 Correct 5 ms 3164 KB Output is correct
14 Correct 8 ms 3164 KB Output is correct
15 Correct 7 ms 3160 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 2652 KB Output is correct
19 Correct 459 ms 34680 KB Output is correct
20 Correct 444 ms 34664 KB Output is correct
21 Correct 449 ms 34472 KB Output is correct
22 Correct 388 ms 34660 KB Output is correct
23 Correct 517 ms 34480 KB Output is correct
24 Correct 281 ms 30268 KB Output is correct
25 Correct 258 ms 30244 KB Output is correct
26 Correct 252 ms 30284 KB Output is correct
27 Correct 265 ms 30292 KB Output is correct
28 Correct 276 ms 30336 KB Output is correct
29 Correct 253 ms 30208 KB Output is correct
30 Correct 286 ms 30324 KB Output is correct
31 Correct 266 ms 30296 KB Output is correct
32 Correct 280 ms 30236 KB Output is correct
33 Correct 268 ms 30300 KB Output is correct
34 Correct 217 ms 30312 KB Output is correct
35 Correct 248 ms 30328 KB Output is correct
36 Correct 241 ms 30332 KB Output is correct
37 Correct 224 ms 30336 KB Output is correct
38 Correct 247 ms 30276 KB Output is correct
39 Correct 240 ms 31608 KB Output is correct
40 Correct 154 ms 22756 KB Output is correct
41 Correct 127 ms 10068 KB Output is correct

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 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 2392 KB Output is correct
7 Correct 2 ms 2396 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 3 ms 2648 KB Output is correct
12 Correct 5 ms 3164 KB Output is correct
13 Correct 5 ms 3164 KB Output is correct
14 Correct 8 ms 3164 KB Output is correct
15 Correct 7 ms 3160 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 2652 KB Output is correct
19 Execution timed out 3034 ms 152820 KB Time limit exceeded
20 Halted 0 ms 0 KB -