oj.uz

Submission #1002980

# Submission time Handle Problem Language Result Execution time Memory
1002980 2024-06-19T21:50:02 Z hyakup Autobahn (COI21_autobahn) C++17
50 / 100
 1000 ms 365872 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]; 
        }

        inline 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;
            if( aux2 ){
                sum[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); 
            if( aux2 ){
                lazy_sum[l[pos]] = lazy_sum[r[pos]] = 0; 
            }
            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 ); 
            if( !traversou ) sum[pos] = min( sum[l[pos]], sum[r[pos]] ); 
            else sum[pos] = sum[l[pos]] + sum[r[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 );   
            if( sum[pos] >= K ){
                lazy_tam[pos] = 1; 
                refresh( pos, ini, fim, 1 ); 
                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]];
            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; scanf(" %d %d %d", &n, &k, &x ); 
    K = k; 
    for( int i = 1; i <= n; i++ ){
        scanf("%d %d %d", &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 ) ), seg.query( 1, 1, inf, max( 1, r[i] - x + 1), r[i] ) }); 
    }
    cout << resp << '\n';
}

Compilation message

autobahn.cpp: In function 'int main()':
autobahn.cpp:112:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     int n, k, x; scanf(" %d %d %d", &n, &k, &x );
      |                  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
autobahn.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         scanf("%d %d %d", &l[i], &t[i], &r[i] );
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 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 1 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 348 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 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 1 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 604 KB Output is correct
13 Correct 2 ms 476 KB Output is correct
14 Correct 3 ms 476 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 2 ms 560 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 604 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 348 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 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 1 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 604 KB Output is correct
13 Correct 2 ms 476 KB Output is correct
14 Correct 3 ms 476 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 2 ms 560 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 604 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 1071 ms 365872 KB Time limit exceeded
22 Halted 0 ms 0 KB -