Submission #400957

#	Time	Username	Problem	Language	Result	Execution time	Memory
400957		NintsiChkhaidze	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3052 ms	1996 KiB

sortbooks

#include<bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
using namespace std;
const int N = 200005;
int a[N],id[N];
pair <int,int> b[N];
bool go(int l,int r,int L,int R){
    bool d1=0,d2=0;
    if (l <= r) d1 = 1;
    if (L <= R) d2 = 1;
    if (d1 == d2) return 0;
    
    if (l > r) swap(l,r);
    if (L > R) swap(L,R);
    
    if (l < L && L < r) return 1;
    if (L < l && l < R) return 1;
    if (l == L || r == R) return 1;
    return 0;
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n,m;
    cin>>n>>m;
    
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=m;i++){
        int l,r,k;
        cin>>l>>r>>k;
        
        for (int j=l;j<=r;j++) 
            b[j] = {a[j],j};
        
        sort(b + l,b + r + 1);
        for (int j = l; j <= r; j++) 
            id[b[j].s] = j;
        
        bool q = 1;
        for (int j = l; j <= r; j++){
            for (int d = j + 1; d <= r; d++){
                if (a[j] + a[d] <= k) continue;
                bool check = go(j,id[j],d,id[d]);
                if (check) {q=0; break;}
            }
            if (!q) break;
        }
        cout<<q<<"\n";
    }
}

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