제출 #1284593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284593		Iwantbemaster	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	834 ms	81752 KiB

sortbooks

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ff first
#define ss second
#define tobit(n) bitset<(int)30>(n)
typedef unsigned long long ull;
#define all(v) (v).begin(), (v).end()
#pragma GCC optimize("Ofast","inline","-ffast-math")
#define rtt(v) rotate(vec.begin(), vec.begin() + k, vec.end()); //move k elements back
vector<int> dx = {1, -1, 0, 0, 1, 1, -1, -1}, dy = {0, 0, 1, -1, 1, -1, 1, -1};
vector<pair<int, int>> DX = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
const vector<pair<int, int>> ANS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
const int MOD = 1e9 + 7, N = (int)1e6, inf = numeric_limits<int>::max();
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void IO(string str_ = ""){
    if((int)str_.size()){
        freopen((str_ + ".in").c_str(), "r", stdin);
        freopen((str_ + ".out").c_str(), "w", stdout);
    }
}
void HASH(){
    const int k = 31, mod = 1e9+7;
    string s = "abacabadaba";
    long long h = 0, m = 1;
    for(auto c : s){
        int x = (int) (c - 'a' + 1);
        h = (h + m * x) % mod;
        m = (m * k) % mod;
    }
}
void rabinKarp(string pattern, string str, int q){
    int m = pattern.size(), n = str.size();
    int i, j, p = 0, t = 0, h = 1, d = 256;
    for(i = 0; i < m - 1; i++) h = (h * d) % q;
    for(i = 0; i < m; i++) p = (d * p + pattern[i]) % q, t = (d * t + str[i]) % q;
    for(i = 0; i <= n - m; i++){
        if(p == t){
            for(j = 0; j < m; j++){
                if(str[i + j] != pattern[j]) break;
            } if(j == m) cout << "Pattern found at index " << i << endl;
        } if(i < n - m){
            t = (d * (t - str[i] * h) + str[i + m]) % q;
            if(t < 0) t = (t + q);
        }
    }
}
void ustaw(int v, int x, vector<int> &tr){
    v += 1 << 20; tr[v] = x; v /= 2;
    while(v > 0) tr[v] = max(tr[v * 2], tr[v * 2 + 1]), v /= 2;
}
int maks(int v, int p, int k, vector<int> &tr, int a, int b){
    if(a <= p && k <= b) return tr[v];
    if(a > k || b < p) return 0;
    return max(maks(v * 2, p, (p + k) / 2, tr, a, b), maks(v * 2 + 1, (p + k) / 2 + 1, k, tr, a, b));
}
signed main(){ // clock_t the_time = clock(); double t_;
	IO(""); int n, m; cin >> n >> m;
    vector<int> w (n, 0);
    for(int i = 0; i < n; i++) cin >> w[i];
    vector<pair<int, int>> p (n);
    stack<pair<int, int>> s;
    for(int i = 0; i < n; i++){
        while(!s.empty() && (s.top().second <= w[i])) s.pop();
        if(!s.empty()) p[i] = {s.top().first, s.top().second + w[i]};
        else p[i] = {-1, -1};
        s.emplace(i, w[i]);
    } vector<pair<pair<int, int>, pair<int, int>>> x (m);
    for(int i = 0; i < m; i++){
        cin >> x[i].ff.ss >> x[i].ff.ff >> x[i].ss.ff;
        x[i].ss.ss = i; x[i].ff.ff--; x[i].ff.ss--;
    } sort(x.begin(), x.end());
    vector<int> tr (1<<21, 0);
    int in = 0;
    vector<int> wy (m, 0);
    for(int i = 0; i < n; i++){
        if(p[i].ff != -1) ustaw(p[i].ff, p[i].ss, tr);
        while(in < m && (x[in].first.first == i)){
            wy[x[in].ss.ss] = maks(1, 0, (1 << 20) - 1, tr, x[in].ff.ss, i) <= (x[in].ss.ff); in++;
        }
    } for(int i : wy) cout << i << '\n';
    // t_ = double(clock() - the_time) / CLOCKS_PER_SEC; cout << fixed << setprecision(16)<<  t_ << " sec.";
}
const int fastIO = [](){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    return 0;
}();
/*

    Открыть терминал: F5

    Закрыть терминал: F6

    Спрятать/показать терминал: F7

    Скомпилировать и запустить: F9

    Только запустить: F12

*/

컴파일 시 표준 에러 (stderr) 메시지

sortbooks.cpp: In function 'void IO(std::string)':
sortbooks.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen((str_ + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen((str_ + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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