Submission #331936

#	Time	Username	Problem	Language	Result	Execution time	Memory
331936		mat_v	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3090 ms	41580 KiB

sortbooks

#include <bits/stdc++.h>
#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define pb push_back
#define maxn 200005

using namespace std;
typedef long long ll;

int n,m;
int niz[maxn];

int seg[4 * maxn];
vector<int> mst[4 * maxn];

void merg(int x, int y, int z){
    int br1 = 0;
    int br2 = 0;
    int p1 = mst[y].size();
    int p2 = mst[z].size();
    while(br1 < p1 || br2 < p2){
        if(br1 == p1){
            mst[x].pb(mst[z][br2]);
            br2++;
            continue;
        }
        if(br2 == p2){
            mst[x].pb(mst[y][br1]);
            br1++;
            continue;
        }
        if(mst[y][br1] < mst[z][br2])mst[x].pb(mst[y][br1]);
        else mst[x].pb(mst[z][br2]);
        if(mst[y][br1] < mst[z][br2])br1++;
        else br2++;
    }
}

void init(int node, int l, int r){
    if(l == r){
        seg[node] = niz[l];
        mst[node].pb(niz[l]);
        return;
    }
    int mid = (l + r) / 2;
    init(node * 2, l, mid);
    init(node * 2 + 1, mid + 1, r);
    merg(node, node * 2, node * 2 + 1);
    seg[node] = max(seg[node * 2], seg[node * 2 + 1]);
}

int nadji(int node, int targ){
    if(mst[node][0] >= targ)return -1e7;
    int l = 0;
    int r = mst[node].size();
    r--;
    while(l < r){
        int mid = (l + r + 1) / 2;
        if(mst[node][mid] < targ)l = mid;
        else r = mid - 1;
    }
    return mst[node][l];
}


int query(int node, int l, int r, int levo, int desno, int targ){
    if(desno < l || r < levo)return -1e7;
    if(l >= levo && r <= desno){
        return nadji(node, targ);
    }
    int mid = (l + r) / 2;
    return max(query(node * 2, l, mid, levo, desno, targ), query(node * 2 + 1, mid + 1, r, levo, desno, targ));
}
int querymax(int node, int l, int r, int levo, int desno){
    if(desno < l || r < levo)return -1e9;
    if(l >= levo && r <= desno)return seg[node];
    int mid = (l + r) / 2;
    return max(querymax(node * 2, l, mid, levo, desno), querymax(node * 2 + 1, mid + 1, r, levo, desno));
}


int resi(int node, int l, int r, int levo, int desno){
    if(levo == desno)return -1e7;
    if(desno < l || r < levo)return -1e7;
    if(l == r)return -1e7;
    int mid = (l + r) / 2;
    if(mid < levo)return resi(node * 2 + 1, mid + 1, r, levo, desno);
    if(mid + 1 > desno)return resi(node * 2, l, mid, levo, desno);
    ll tr = resi(node * 2, l, mid, levo, mid);
    ll tr2 = resi(node * 2 + 1, mid + 1, r, mid + 1, desno);
    ll l1 = querymax(node * 2, l, mid, levo, mid);
    ll r1 = query(node * 2 + 1, mid + 1, r, mid + 1, desno, l1);
    return max(tr, max(tr2, l1 + r1));

}



int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> m;
    ff(i,1,n){
        cin >> niz[i];
    }
    init(1,1,n);
    ff(i,1,m){
        int l,r,x;
        cin >> l >> r >> x;
        int sta = resi(1,1,n,l,r);
        if(sta > x)cout << 0 << "\n";
        else cout << 1 << "\n";
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sortbooks.cpp:103:5: note: in expansion of macro 'ff'
  103 |     ff(i,1,n){
      |     ^~
sortbooks.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
sortbooks.cpp:107:5: note: in expansion of macro 'ff'
  107 |     ff(i,1,m){
      |     ^~

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