Submission #1002771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002771		hyakup	Autobahn (COI21_autobahn)	C++17	50 / 100	962 ms	524288 KiB

autobahn

#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 ){
            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; 
            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 ); 
            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); 
                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 ){
            refresh( pos, ini, fim ); 
            if( l[pos] == 0 && r[pos] == 0 ){
                if( qtd[pos] >= K ) lazy_tam[pos] = 1; 
                refresh( pos, ini, fim ); 
                return; 
            }
            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 ); 
            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]; 
        // bug(i); 
        seg.update( 1, 1, inf, l[i], r[i], 1 ); 
    }
    seg.traverse( 1, 1, inf ); 
    for( int i = 1; i <= n; i++ ){
        // bug(i); 
        // bug(l[i] + t[i]); 
        // bug(r[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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 0 / 50