oj.uz

Submission #671747

# Submission time Handle Problem Language Result Execution time Memory
671747 2022-12-13T16:21:42 Z Username4132 Autobahn (COI21_autobahn) C++14
100 / 100
 213 ms 10724 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)

const int MAXN = 1e5+10;
int n, k, x, cn;
int in1[MAXN], in2[MAXN], in3[MAXN], impt[2*MAXN], lv[MAXN], rv[MAXN];
long long pl[MAXN], pr[MAXN];
pii segs[MAXN];
multiset<int> rs;
vector<int> trs, keys;
vector<long long> segsum;

long long find_sum(int x){
    long long lcnt = upper_bound(lv, lv+cn, x) - lv;
    long long rcnt = upper_bound(rv, rv+cn, x) - rv;
    return (lcnt-rcnt)*x + pr[rcnt] - pl[lcnt];
}

long long true_sum(int x){
    int pos = lower_bound(trs.begin(), trs.end(), x) - trs.begin();
    if(pos&1) return segsum[pos>>1] + find_sum(x) - find_sum(trs[pos-1]);
    else return segsum[pos>>1];
}

int main(){
    cin >> n >> k >> x;
    forn(i, n) cin >> in1[i] >> in2[i] >> in3[i], impt[i]=in1[i], impt[n+i]=in3[i]+1, segs[i] = {in1[i], in3[i]+1};
    forn(i, n) if(in1[i]+in2[i]<=in3[i]) lv[cn]=in1[i]+in2[i], rv[cn++]=in3[i]+1;

    sort(segs, segs+n);
    sort(impt, impt+2*n);
    sort(lv, lv+cn);
    sort(rv, rv+cn);
    forn(i, cn) pl[i+1] = pl[i]+lv[i], pr[i+1] = pr[i]+rv[i];

    bool flag=false;
    int cur=0;
    forn(i, 2*n){
        while(cur<n && segs[cur].first<=impt[i]) rs.insert(segs[cur++].second);
        while(!rs.empty() && *rs.begin()<=impt[i]) rs.erase(rs.begin());
        if(flag==true ^ rs.size()>=k){
            trs.push_back(impt[i]);
            flag^=1;
        }
    }

    segsum.assign((trs.size()>>1) +1, 0);
    for(int i=0; i<trs.size(); i+=2){
        segsum[(i>>1) + 1] = find_sum(trs[i+1]) - find_sum(trs[i]) + segsum[i>>1];
    }

    forn(i, trs.size()>>1){
        keys.push_back(trs[i<<1]);
        keys.push_back(trs[i<<1|1]-x);
    }
    forn(i, cn){
        keys.push_back(lv[i]);
        keys.push_back(rv[i]-x);
    }

    long long mx=0;
    for(auto el:keys){
        mx = max(mx, true_sum(el+x) - true_sum(el));
    }

    cout << mx << '\n';
}

Compilation message

autobahn.cpp: In function 'int main()':
autobahn.cpp:46:34: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         if(flag==true ^ rs.size()>=k){
      |                         ~~~~~~~~~^~~
autobahn.cpp:46:16: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   46 |         if(flag==true ^ rs.size()>=k){
      |            ~~~~^~~~~~
autobahn.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0; i<trs.size(); i+=2){
      |                  ~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 2 ms 340 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 209 ms 7704 KB Output is correct
22 Correct 213 ms 10700 KB Output is correct
23 Correct 202 ms 10528 KB Output is correct
24 Correct 207 ms 10652 KB Output is correct
25 Correct 201 ms 10724 KB Output is correct
26 Correct 198 ms 10440 KB Output is correct
27 Correct 188 ms 10428 KB Output is correct
28 Correct 183 ms 10476 KB Output is correct
29 Correct 182 ms 10680 KB Output is correct