oj.uz

Submission #1071326

# Submission time Handle Problem Language Result Execution time Memory
1071326 2024-08-23T06:42:17 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 24744 KB 
//#include <bits/stdc++.h>

#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

#define int long long

const int N = 1e6 + 7;
const int M = 1e16 + 7;

struct custom_hash { //unordered_map<long long, int, custom_hash> safe_map; gp_hash_table<long long, int, custom_hash> safe_hash_table;

    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int binpow(int a, int n, int m) {
    int res = 1;
    while (n) {
        if (n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}

/*inline void factorials(int n) {
    f[0] = 1;
    for(int i = 1; i <= n; i++) {
        f[i] = (f[i - 1] * i) % M;
    }
    invf[n] = binpow(f[n], M - 2, M);
    for(int i = n - 1; i >= 0; i--) {
        invf[i] = (invf[i + 1] * (i + 1)) % M;
    }
}

inline int cnk(int n, int k) {
    if(k > n) {
        return 0;
    }
    return (((f[n] * invf[n - k]) % M) * invf[k]) % M;
} */

int a[N];

inline void Solve() {
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= q; i++) {
        int l, r, w, h = 0;
        cin >> l >> r >> w;
        vector<int> v;
        for(int j = l; j <= r; j++) v.push_back(a[j]);
        for(int j = 0; j < v.size() - 1; j++) {
            int nw = j;
            while(v[nw] > v[nw + 1] and nw < v.size() - 1) {
                if(v[nw] + v[nw + 1] > w) {
                    cout << 0 << '\n';
                    h++;
                    break;
                }
                swap(v[nw], v[nw + 1]);
                nw++;
            }
            if(h > 0) break;
        }
        if(h == 0) cout << 1 << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int t = 1;
    //cin >> t;
    //cout << '\n' << '\n';
    
    while(t--) {
        Solve();
    }
    
    return 0;
}

/*
 Special cases n = 1 or just 1?
 u r using unsigned long long which can't carry negative values?
 what if u r doing the same thing n times, it may cause the TL
 make sure that the size of your massives, vectors are enough
*/

Compilation message

sortbooks.cpp: In function 'void Solve()':
sortbooks.cpp:141:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         for(int j = 0; j < v.size() - 1; j++) {
      |                        ~~^~~~~~~~~~~~~~
sortbooks.cpp:143:44: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |             while(v[nw] > v[nw + 1] and nw < v.size() - 1) {
      |                                         ~~~^~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 16 ms 608 KB Output is correct
13 Correct 18 ms 612 KB Output is correct
14 Correct 32 ms 604 KB Output is correct
15 Correct 31 ms 604 KB Output is correct
16 Correct 106 ms 604 KB Output is correct
17 Correct 52 ms 604 KB Output is correct
18 Correct 80 ms 604 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3026 ms 24744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3054 ms 4488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 16 ms 608 KB Output is correct
13 Correct 18 ms 612 KB Output is correct
14 Correct 32 ms 604 KB Output is correct
15 Correct 31 ms 604 KB Output is correct
16 Correct 106 ms 604 KB Output is correct
17 Correct 52 ms 604 KB Output is correct
18 Correct 80 ms 604 KB Output is correct
19 Execution timed out 3102 ms 7664 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 4 ms 348 KB Output is correct
12 Correct 16 ms 608 KB Output is correct
13 Correct 18 ms 612 KB Output is correct
14 Correct 32 ms 604 KB Output is correct
15 Correct 31 ms 604 KB Output is correct
16 Correct 106 ms 604 KB Output is correct
17 Correct 52 ms 604 KB Output is correct
18 Correct 80 ms 604 KB Output is correct
19 Execution timed out 3026 ms 24744 KB Time limit exceeded
20 Halted 0 ms 0 KB -