oj.uz

Submission #1002852

# Submission time Handle Problem Language Result Execution time Memory
1002852 2024-06-19T20:41:50 Z gabistroeh Autobahn (COI21_autobahn) C++14
0 / 100
 1 ms 860 KB 
    #include<bits/stdc++.h>
    using namespace std;
     
    const int MAXN = 100010;
    int l[MAXN], r[MAXN], t[MAXN], mark[MAXN];
    int v[MAXN];
    int seg[4*MAXN], qtde[4*MAXN];

    int query(int pos, int ini, int fim, int l1, int r1){
        if(r1<ini || l1>fim) return 0;
        if(l1<=ini && r1>=fim) return seg[pos];
        int m = (ini+fim)/2;
        int e=2*pos, d=2*pos+1;
        return query(1, ini, m, l1, r1) + query(d, m+1, fim, l1, r1);
    }


    void build(int pos, int ini, int fim){
        if(ini==fim){
            seg[pos] = v[ini];
            return;
        }
        int m = (ini+fim)/2;
        int e=2*pos, d=2*pos+1;
        build(e, ini, m);
        build(d, m+1, fim);
        seg[pos] = seg[d] + seg[e];
    }

    void build2(int pos, int ini, int fim){
        if(ini==fim){
            seg[pos] = mark[ini];
            return;
        }
        int m = (ini+fim)/2;
        int e=2*pos, d=2*pos+1;
        build(e, ini, m);
        build(d, m+1, fim);
        seg[pos] = min(seg[d], seg[e]);
    }
     
    int main(){
    	int n, k, x;
    	cin >> n >> k >> x;
    	for(int i=0; i<n; i++){
    		cin >> l[i] >> t[i] >> r[i];
    		mark[l[i]]++;
            mark[r[i]+1]--;
    	}
        for(int i=1; i<100001; i++) mark[i] = mark[i-1] + mark[i];
    	for(int i=0; i<n; i++){
    		int tam = r[i] - l[i] + 1;
    		if(t[i]>=tam) continue;
    		int pes = 0;
    		for(int j=l[i]+t[i]; j<=r[i]; j++){
    			if(mark[j]>=k){
    				v[j]++;
    			}
    		}
    	}
        build(1, 1, 1000);
    	//for(int i=1; i<10; i++) cout << v[i] << " ";
    	int resp = 0;
    	for(int i=1; i<=1000-x+1; i++){
    		int cur = query(1, 1, n, i, i+x-1);
            //cout << "de " << i << " ate " << i+x-1 << " deu " << cur << endl;
    		//if(cur>resp) cout << cur << endl;
    		resp = max(resp, cur);
    	}
    	cout << resp;
    }

Compilation message

autobahn.cpp: In function 'int query(int, int, int, int, int)':
autobahn.cpp:13:13: warning: unused variable 'e' [-Wunused-variable]
   13 |         int e=2*pos, d=2*pos+1;
      |             ^
autobahn.cpp: In function 'int main()':
autobahn.cpp:54:11: warning: unused variable 'pes' [-Wunused-variable]
   54 |       int pes = 0;
      |           ^~~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 860 KB Output isn't correct
2 Halted 0 ms 0 KB -