oj.uz

답안 #1002913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1002913 2024-06-19T21:19:27 Z hyakup Autobahn (COI21_autobahn) C++17
50 / 100
 1000 ms 398140 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:
        inline int create(){
            sum.push_back(0); 
            tam.push_back(0); 
            l.push_back(0); 
            r.push_back(0); 
            lazy_sum.push_back(0); 
            lazy_tam.push_back(0);
            return (int)sum.size() - 1; 
        }

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

        inline 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_sum[pos] == 0 && lazy_tam[pos] == 0 ) return; 
            aux1 = lazy_sum[pos]; lazy_sum[pos] = 0; 
            aux2 = lazy_tam[pos]; lazy_tam[pos] = 0;

            tam[pos] += (fim - ini + 1)*aux2;  
            if( !traversou ) sum[pos] += aux1; 
            else sum[pos] += 1LL*tam[pos]*aux1; 
            
             
            if( ini == fim ) return; 
            if( !flag ) return; 
            left(pos); right(pos); 
            lazy_sum[l[pos]] += aux1; 
            lazy_sum[r[pos]] += aux1; 
            lazy_tam[l[pos]] += aux2; 
            lazy_tam[r[pos]] += aux2; 
        }

        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 ){
                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 ); 
            
            sum[pos] = sum[left(pos)] + sum[right(pos)]; 
        }

        void traverse( int pos, int ini, int fim ){
            if( l[pos] == 0 && r[pos] == 0 ){
                refresh( pos, ini, fim, 0 ); 
                if( sum[pos] >= K ) lazy_tam[pos] = 1; 
                refresh( pos, ini, fim, 1 ); 
                sum[pos] = 0; 
                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]];
            sum[pos] = 0; 
            if( pos == 1 ) traversou = true; 
        }

        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> tam, l, r, lazy_sum, lazy_tam; 
        int aux1, aux2; 
        bool traversou = false; 
} seg; 

const int maxn = 1e5 + 10; 
int l[maxn], t[maxn], r[maxn]; 

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);  
    int n, k, x; cin >> n >> k >> x; 
    K = k; 
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 360 KB Output is correct
7 Correct 1 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 360 KB Output is correct
7 Correct 1 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 2 ms 600 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 604 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 604 KB Output is correct
19 Correct 3 ms 604 KB Output is correct
20 Correct 2 ms 624 KB Output is correct

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 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 360 KB Output is correct
7 Correct 1 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 2 ms 600 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 604 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 604 KB Output is correct
19 Correct 3 ms 604 KB Output is correct
20 Correct 2 ms 624 KB Output is correct
21 Execution timed out 1066 ms 398140 KB Time limit exceeded
22 Halted 0 ms 0 KB -