Submission #895902

#	Time	Username	Problem	Language	Result	Execution time	Memory
895902		1075508020060209tc	Two Antennas (JOI19_antennas)	C++14	13 / 100	1402 ms	524288 KiB

antennas

#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=max(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 pl){
if(tr[nw].l>=pl){
    return tr[nw].mx;
}
if(tr[nw].r<pl){
    return -1;
}
return max(qmx(nw*2,pl),qmx(nw*2+1,pl));
}


int n;int Q;
int ar[500005];
int br[500005];
int hr[500005];
int lar[500005];
int rar[500005];
vector<pair<int,int>>e[500005];
vector<int>qe[500005];
int ans[500005];
signed main(){

cin>>n;
for(int i=1;i<=n;i++){
    cin>>hr[i]>>ar[i]>>br[i];
}
cin>>Q;
for(int i=1;i<=Q;i++){
    cin>>lar[i]>>rar[i];
    qe[rar[i]].push_back(i);
}
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        int d=abs(i-j);
        if(d>=ar[i]&&d<=br[i]&&d>=ar[j]&&d<=br[j]){
            e[j].push_back({i,abs(hr[i]-hr[j])});
        }
    }
}
buildtr(1,1,n);
for(int i=1;i<=n;i++){
    for(int j=0;j<e[i].size();j++){
        upd(1,e[i][j].first,e[i][j].second);
    }
    for(int j=0;j<qe[i].size();j++){
        int id=qe[i][j];
        ans[id]=qmx(1,lar[id]);
    }
}
for(int i=1;i<=Q;i++){
    cout<<ans[i]<<"\n";
}

}

Compilation message (stderr)

antennas.cpp: In function 'int main()':
antennas.cpp:71:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int j=0;j<e[i].size();j++){
      |                 ~^~~~~~~~~~~~
antennas.cpp:74: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]
   74 |     for(int j=0;j<qe[i].size();j++){
      |                 ~^~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 65