oj.uz

Submission #1002885

# Submission time Handle Problem Language Result Execution time Memory
1002885 2024-06-19T21:00:55 Z hyakup Autobahn (COI21_autobahn) C++17
50 / 100
 1000 ms 398392 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define bug(x) cout << #x << " " << x << endl;

const int inf = 1e9 + 10; 

int K; 

class sparse_seg{
    public:
        int create(){
            sum.push_back(0); 
            qtd.push_back(0); 
            tam.push_back(0); 
            l.push_back(0); 
            r.push_back(0); 
            lazy_qtd.push_back(0); 
            lazy_sum.push_back(0); 
            lazy_tam.push_back(0);
            return (int)sum.size() - 1; 
        }

        int left( int pos ){
            if( l[pos] == 0 ){ int aux = create(); l[pos] = aux; }
            return l[pos]; 
        }

        int right( int pos ){
            if( r[pos] == 0 ){ int aux = create(); r[pos] = aux; }
            return r[pos]; 
        }

        void refresh( int pos, int ini, int fim, int flag ){
            if( lazy_qtd[pos] == 0 && lazy_sum[pos] == 0 && lazy_tam[pos] == 0 ) return; 
            aux1 = lazy_qtd[pos]; lazy_qtd[pos] = 0; 
            aux2 = lazy_sum[pos]; lazy_sum[pos] = 0; 
            aux3 = lazy_tam[pos]; lazy_tam[pos] = 0; 
            qtd[pos] += aux1; 
            tam[pos] += (fim - ini + 1)*aux3; 
            sum[pos] += 1LL*tam[pos]*aux2; 
            if( ini == fim ) return; 
            if( !flag ) return; 
            left(pos); right(pos); 
            lazy_qtd[l[pos]] += aux1; 
            lazy_qtd[r[pos]] += aux1; 
            lazy_sum[l[pos]] += aux2; 
            lazy_sum[r[pos]] += aux2; 
            lazy_tam[l[pos]] += aux3; 
            lazy_tam[r[pos]] += aux3; 
        }

        void merge( int pos ){
            sum[pos] = sum[left(pos)] + sum[right(pos)]; 
            qtd[pos] = qtd[left(pos)] + qtd[right(pos)]; 
        }

        void update( int pos, int ini, int fim, int ki, int kf, int t ){
            refresh( pos, ini, fim, 1 ); 
            if( ki > fim || ini > kf ) return; 
            if( ki <= ini && fim <= kf ){
                if( t == 1 ) lazy_qtd[pos]++; 
                else lazy_sum[pos]++; 
                refresh(pos, ini, fim, 1); 
                return; 
            }
            int mid = (ini + fim)/2; 
            update( left(pos), ini, mid, ki, kf, t); 
            update( right(pos), mid + 1, fim, ki, kf, t ); 
            merge( pos ); 
            // if( t == 2 ) cout << ini << " " << fim << endl;
            // if( t == 2 ) bug(sum[pos]);
        }

        void traverse( int pos, int ini, int fim ){
            if( l[pos] == 0 && r[pos] == 0 ){
                refresh( pos, ini, fim, 0 ); 
                if( qtd[pos] >= K ) lazy_tam[pos] = 1; 
                refresh( pos, ini, fim, 1 ); 
                return; 
            }
            refresh( pos, ini, fim, 1 ); 
            int mid = (ini + fim)/2; 
            traverse( l[pos], ini, mid ); traverse( r[pos], mid + 1, fim ); 
            tam[pos] = tam[l[pos]] + tam[r[pos]];
            // cout << ini << " " << fim << endl;
            // bug(tam[pos]); 
        }

        ll query( int pos, int ini, int fim, int ki, int kf ){
            refresh( pos, ini, fim, 1 ); 
            if( ki > fim || ini > kf ) return 0; 
            if( ki <= ini && fim <= kf ){  return sum[pos];} 
            int mid = (ini + fim)/2; 
            return query( left(pos), ini, mid, ki, kf ) + query( right(pos), mid + 1, fim, ki, kf ); 
        }
        sparse_seg(){ create(); create(); }
    private:
        vector<ll> sum; 
        vector<int> qtd, tam, l, r, lazy_qtd, lazy_sum, lazy_tam; 
        int aux1, aux2, aux3; 
} seg; 

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);  
    int n, k, x; cin >> n >> k >> x; 
    K = k; 
    vector<int> l(n + 1), t(n + 1), r(n + 1); 
    for( int i = 1; i <= n; i++ ){
        cin >> l[i] >> t[i] >> r[i]; 
        seg.update( 1, 1, inf, l[i], r[i], 1 ); 
    }
    seg.traverse( 1, 1, inf ); 
    for( int i = 1; i <= n; i++ ) if( l[i] + t[i] <= r[i] ) seg.update( 1, 1, inf, l[i] + t[i], r[i], 2 ); 
    
    ll resp = 0; 
    for( int i = 1; i <= n; i++ ){
        resp = max( resp, seg.query( 1, 1, inf, l[i] + t[i], min( l[i] + t[i] + x - 1, inf ) ) ); 
        resp = max( resp, seg.query( 1, 1, inf, max( 1, r[i] - x + 1), r[i] ) ); 
    }
    cout << resp << endl;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 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 3 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 3 ms 604 KB Output is correct
17 Correct 3 ms 600 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 576 KB Output is correct
20 Correct 3 ms 604 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 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 3 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 3 ms 604 KB Output is correct
17 Correct 3 ms 600 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 576 KB Output is correct
20 Correct 3 ms 604 KB Output is correct
21 Execution timed out 1048 ms 398392 KB Time limit exceeded
22 Halted 0 ms 0 KB -