| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1002851 | gabistroeh | Autobahn (COI21_autobahn) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
return query(1, ini, m, l1, r1) + query(1, m+1, fim, l1, r1);
}
coid update(int ini, int )
void build(int pos, int ini, int fim){
if(ini==fim){
seg[pos] = v[ini];
return;
}
int m = (ini+fim)/2;
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;
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;
}