제출 #905874

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
905874		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3028 ms	61220 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'
#define int long long
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 = 5e5 + 100;
const int B = 1e6 + 1;
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[B];
int tree[B];
void update(int ind,int x,int tl,int tr,int v) {
    if(tl == tr) {
        tree[v] = x;
        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]);
}   
int get(int l,int r,int tl,int tr,int v) {
    if(l > tr || tl > r) return 0;
    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 <int,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] = {};
    for(int i = 1;i <= q;i++) {
        int r = p[i].f;
        while(it <= r) {
            for(int j = 1;j <= it;j++) {
                if(a[j] > a[it]) {
                    update(j,a[j] + a[it],1,n,1);
                }
            }
            it++;
        }
        int l = p[i].s.f;
        int 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, это сложно
            О-о-она застыла в ожидании солнца-а-а-а
            Но я не думаю что сможет согреть
            Её ледяную душу, остаётся лишь смотреть (А, а, а-а-а-а)
      
            Все твои слёзы просто превращаю в лёд
            Я-я-я спрячу сердце, его никто не найдёт (Не найдёт)
            Не вижу смысла кончить этот эпизод (—З-з-з-од)
            Я вижу выход, но не могу найти вход (И-и)
            Все твои слёзы просто превращаю в лё-лё-лёд
            Я-я спрячу сердце, его никто не найдёт
            Не вижу смысла кончить этот эпизод
            Я вижу выход, но не могу найти вход
            Твои слёзы просто-просто пре— в лёд
            Я-я-я-я прячу сердце, его-его не найдёт (Не найд—, не най—)
            Не вижу смысла кончить-кончить эпизод (А-а-а-а, а-а-а-а)
            Я вижу выход, но не—, но не— найти вход
      
            (—Ход-ход-ход-ход-ход, вход) Все твои слёзы просто превращаю в лёд
            Я-я-я-я спрячу сердце, его никто не найдёт (Не найдёт)
            Не вижу смысла кончить этот эпизод (—З-з-з-од)
            Я вижу выход, но не могу-гу най— вход
            
            */

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23