Submission #1301230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301230		BuiDucManh123	Pilot (NOI19_pilot)	C++20	100 / 100	900 ms	62096 KiB

pilot

#include <bits/stdc++.h>
#define TN ""
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define ll long long
#define int ll
int n, q, ans, res[1000009];
set<pair<int, int>> st;
int cost(int x){
    return x * (x + 1) / 2;
}
void add(int x){
    auto id = st.upper_bound({x, 1e9});
    id--;
    int l = id->first, r = id->second;
    ans -= cost(r - l + 1);
    st.erase(id);
    if(l < x){
        st.insert({l, x - 1});
        ans += cost(x - l);
    }
    if(x < r){
        st.insert({x + 1, r});
        ans += cost(r - x);
    }
}
void Solve(){
    cin >> n >> q;
    vector<pair<int, int>> v;
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        v.push_back({x, i});
    }
    ans = n * (n + 1) / 2;
    for(int i = 1; i <= q; i++){
        int x;
        cin >> x;
        v.push_back({x, i + n});
    }
    sort(v.begin(), v.end(), greater<>());
    st.insert({1, n});
    for(pair<int, int> x : v){
        if(x.second <= n){
            add(x.second);
        }else{
            res[x.second - n] = ans;
        }
    }
    for(int i = 1; i <= q; i++){
        cout << res[i] << "\n";
    }
}
signed main() {
    if(fopen(TN".inp", "r")){
        freopen(TN".inp", "r", stdin);
        freopen(TN".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test = 1;
    //cin >> test;
    while(test--){
        Solve();
    }
    return 0;
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         freopen(TN".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
pilot.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen(TN".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11