Submission #905963

#	Time	Username	Problem	Language	Result	Execution time	Memory
905963		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3092 ms	154724 KiB

sortbooks

#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 = 1e6 + 1000000;
const int B = 4e6 + 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,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) >> 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] << "\n";
}

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

Compilation message (stderr)

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:46: warning: bad option '-fprofile-values' to attribute 'optimize' [-Wattributes]
  134 | void update(int ind,int x,int tl,int tr,int v) {
      |                                              ^
sortbooks.cpp:134:46: warning: bad option '-ffunction-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:134:46: warning: bad option '-fdata-sections' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:134:46: warning: bad option '-fbranch-target-load-optimize' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:134:46: warning: bad option '-fbranch-target-load-optimize2' to attribute 'optimize' [-Wattributes]
sortbooks.cpp:134:46: 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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23