oj.uz

Submission #1002746

# Submission time Handle Problem Language Result Execution time Memory
1002746 2024-06-19T19:16:42 Z teesla Autobahn (COI21_autobahn) C++17
50 / 100
 1000 ms 85288 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> ii;
typedef pair<int, ii> iii;

struct seg{

    vector<int> extra, qnt;
    int n;
    seg(){};
    seg(int x){n = x; qnt.assign(4*(x+1), 0); extra.assign(4*(x+1), 0);}

    void addQnt(int pos, int i, int f, int l, int r){
        if(l<=i and f<=r){
            qnt[pos] += 1; 
            return;
        }
        int meio = (i+f)/2;
        if(l <=meio) addQnt(2*pos+1, i, meio, l, r);
        if(r > meio) addQnt(2*pos+2, meio+1, f, l, r);
        return;
    }
    void addExtra(int pos, int i, int f, int l, int r){
        if(l <= i and f<= r){
            extra[pos] += 1;
            return;
        }
        int meio = (i+f)/2;
        if(l <= meio) addExtra(2*pos+1, i, meio, l, r);
        if(r > meio) addExtra(2*pos+2, meio+1, f, l, r);
        return;
    }
    pair<int,int> query(int pos, int i, int f, int idx){
        if(i == f and i == idx){
            return {extra[pos], qnt[pos]};
        }
        int meio = (i+f)/2;
        
        pair<int, int> res;
        if(idx <= meio) res = query(2*pos+1, i, meio, idx);
        else res = query(2*pos+2, meio + 1, f, idx);

        res.first += extra[pos];
        res.second += qnt[pos];
        return res;
    }

    void addQnt(int l, int r){ addQnt(0,0,n,l,r); return;}
    void addExtra(int l, int r) {addExtra(0,0,n,l,r); return;}
    pair<int,int> query(int idx){
        return query(0,0,n,idx);
    }
};

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,k,x; cin >> n >> k >> x;
    vector<int> aux;
    vector<iii> v;

    for(int i=0; i<n; i++){
        int l,t,r; cin >> l >> t >> r;
        aux.push_back(l-1);
        aux.push_back(l); aux.push_back(l+t-1); aux.push_back(l + t); aux.push_back(r); aux.push_back(r + 1);
        v.push_back({l, {t,r}});
    }

    sort(aux.begin(), aux.end());
    int cont = 0;
    map<int,int> comp;

    for(auto i: aux){
        if(comp[i] == 0){
            cont++;
            comp[i] = cont;
        }
    }

    seg tree(cont);

    for(auto i: v){
        int l = i.first, t = i.second.first, r = i.second.second;
        //cout << endl << endl;
        
        tree.addQnt(comp[l],comp[r]);
        tree.addExtra(comp[l+t], comp[r]);
    }

    int maior = 0;
    int sum = 0;

    int i=0, f = 1;

    ii aa = tree.query(comp[aux[0]]);
    if(aa.second >= k){sum += aa.first; maior = sum;}

    while(f< aux.size()){
        int l = aux[i], r = aux[f];
        if(aux[f] == aux[f-1]){
            f++;
            continue;
        }

        if(r - l >= x){
            int anterior = aux[f-1];
            int sobra = anterior-l + 1;
            int outro = sum;

            sobra = x - sobra;

            ii valorAnterior = tree.query(comp[anterior]);
            if(valorAnterior.second >= k){
                outro += sobra*valorAnterior.first;
            }
            maior = max(maior, outro);

            sobra = aux[i+1] - aux[i];
            valorAnterior = tree.query(comp[aux[i]]);
            if(valorAnterior.second >= k){
                sum -= sobra*valorAnterior.first;
            }

            i++;

        }
        else{
            int anterior = aux[f-1];
            int sobra = aux[f] - aux[f-1] -1;
            ii valorAnterior = tree.query(comp[aux[f-1]]);
            if(valorAnterior.second >= k){
                sum += sobra*valorAnterior.first;
            }
            ii valorAtual = tree.query(comp[aux[f]]);
            if(valorAtual.second >= k){
                sum += valorAtual.first;
            }
            maior = max(sum, maior);
            f++;
        }
    }
    sum = 0;

    f = aux.size()-1; i = aux.size() - 2;
    aa = tree.query(comp[aux[f]]);
    if(aa.second >= k){sum += aa.first; maior = max(maior, sum);}

    while(i>=0){
        int l = aux[i], r = aux[f];
        if(aux[i] == aux[i+1]){
            i--; continue;
        }

        if(r - l >= x){
            int anterior = aux[i+1];
            int sobra = r - anterior + 1;
            sobra = x-sobra;
            int outro = sum;

            ii valorAnterior = tree.query(comp[anterior]);
            if(valorAnterior.second >= k){
                outro += sobra*valorAnterior.first;
            }

            maior = max(maior, outro);

            sobra = aux[f] - aux[f-1];
            valorAnterior = tree.query(comp[aux[f]]);
            if(valorAnterior.second >= k){
                sum -= sobra*valorAnterior.first;
            }
            f--;
        }
        else{
            int sobra = aux[i+1] - aux[i] - 1;
            ii valorAnterior = tree.query(comp[aux[i+1]]);
            if(valorAnterior.second >= k){
                sum += sobra*valorAnterior.first;
            }
            ii valorAtual = tree.query(comp[aux[i]]);
            if(valorAtual.second >= k){
                sum += valorAtual.first;
            }
            maior = max(maior, sum);
            i--;
        }
    }

    cout << maior << endl;

}

Compilation message

autobahn.cpp: In function 'int main()':
autobahn.cpp:101:12: 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]
  101 |     while(f< aux.size()){
      |           ~^~~~~~~~~~~~
autobahn.cpp:131:17: warning: unused variable 'anterior' [-Wunused-variable]
  131 |             int anterior = aux[f-1];
      |                 ^~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 668 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 668 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 2 ms 604 KB Output is correct
21 Execution timed out 1053 ms 85288 KB Time limit exceeded
22 Halted 0 ms 0 KB -