oj.uz

Submission #895986

# Submission time Handle Problem Language Result Execution time Memory
895986 2023-12-31T11:13:24 Z 1075508020060209tc Two Antennas (JOI19_antennas) C++14
22 / 100
 423 ms 45016 KB 
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
struct SGTR{
int l;int r;int mx;
}tr[800005];
void buildtr(int nw,int l,int r){
tr[nw].l=l;tr[nw].r=r;
tr[nw].mx=-1;
if(l==r){
    return;
}
int mi=(l+r)/2;
buildtr(nw*2,l,mi);
buildtr(nw*2+1,mi+1,r);
}
void upd(int nw,int pl,int v){
if(tr[nw].l==pl&&tr[nw].r==pl){
    tr[nw].mx=v;
    return;
}
if(tr[nw].l>pl||tr[nw].r<pl){return;}
upd(nw*2,pl,v);
upd(nw*2+1,pl,v);
tr[nw].mx=max(tr[nw*2].mx,tr[nw*2+1].mx);
}
int qmx(int nw,int l,int r){
if(tr[nw].l>=l&&tr[nw].r<=r){
    return tr[nw].mx;
}
if(tr[nw].r<l||tr[nw].l>r){
    return -1;
}
return max(qmx(nw*2,l,r),qmx(nw*2+1,l,r));
}
int n;
int hr[200005];
int ar[200005];
int br[200005];
vector<int>event[500005];
int ans;
void solve(){
buildtr(1,1,n);

for(int i=1;i<=n;i++){
    event[i+ar[i]].push_back(i);
    event[i+br[i]+1].push_back(-i);
}

for(int i=1;i<=n;i++){
    for(int j=0;j<event[i].size();j++){
        int id=abs(event[i][j]);
        if(event[i][j]>0){
            upd(1,id,hr[id]);
        }else{
            upd(1,id,-1);
        }
    }
    ans=max(ans,-hr[i]+qmx(1,i-br[i],i-ar[i]));
}


}


signed main(){
cin>>n;
for(int i=1;i<=n;i++){
    cin>>hr[i]>>ar[i]>>br[i];
}
solve();
reverse(ar+1,ar+n+1);
reverse(br+1,br+n+1);
reverse(hr+1,hr+n+1);
for(int i=0;i<=n*2;i++){
    event[i].clear();
}
solve();
cin>>n;
cin>>n;
cin>>n;
cout<<ans<<"\n";


}

Compilation message

antennas.cpp: In function 'void solve()':
antennas.cpp:54:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int j=0;j<event[i].size();j++){
      |                 ~^~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 11.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 43076 KB Output is correct
2 Correct 365 ms 44752 KB Output is correct
3 Correct 261 ms 40208 KB Output is correct
4 Correct 364 ms 44628 KB Output is correct
5 Correct 148 ms 30036 KB Output is correct
6 Correct 378 ms 44624 KB Output is correct
7 Correct 312 ms 42664 KB Output is correct
8 Correct 349 ms 44632 KB Output is correct
9 Correct 58 ms 21332 KB Output is correct
10 Correct 373 ms 45016 KB Output is correct
11 Correct 203 ms 32736 KB Output is correct
12 Correct 423 ms 44740 KB Output is correct
13 Correct 235 ms 42948 KB Output is correct
14 Correct 232 ms 43264 KB Output is correct
15 Correct 232 ms 42792 KB Output is correct
16 Correct 224 ms 43108 KB Output is correct
17 Correct 249 ms 43264 KB Output is correct
18 Correct 236 ms 42324 KB Output is correct
19 Correct 258 ms 43060 KB Output is correct
20 Correct 232 ms 42820 KB Output is correct
21 Correct 227 ms 43476 KB Output is correct
22 Correct 234 ms 42956 KB Output is correct
23 Correct 241 ms 42956 KB Output is correct
24 Correct 236 ms 42284 KB Output is correct

Subtask #4
0 / 65.0

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