Submission #385817

#	Time	Username	Problem	Language	Result	Execution time	Memory
385817		i_am_noob	Two Antennas (JOI19_antennas)	C++17	100 / 100	1031 ms	30084 KiB

antennas

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;

#define ll long long
#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif

inline char readchar(){
    const int maxn=1000000;
    static char buf[maxn],*p=buf,*q=buf;
    if(p==q&&(q=(p=buf)+fread(buf,1,maxn,stdin))==buf) return EOF;
    else return *p++;
}
inline int readint(){
    int c=readchar(),x=0,neg=0;
    while((c<'0'||c>'9')&&c!='-'&&c!=EOF) c=readchar();
    if(c=='-') neg=1,c=readchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=readchar();
    return neg?-x:x;
}

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=200005;
//i_am_noob
const int K=455;
int n,h[maxn],a[maxn],b[maxn],q,ans[maxn];

struct query{
    int l,r,id;
}qry[maxn];

struct event{
    int id,pos;
    bool op;
};
vector<event> ev;

vector<int> vec[maxn/K+5];
int cur,cur1,vals[maxn],valb[maxn/K+5],cur2[maxn/K+5],minn[maxn/K+5],maxx[maxn/K+5];
multiset<int> st[maxn/K+5];
bool in[maxn];

inline void Insert(int id){
    st[id/K].insert(h[id]);
}

inline void Erase(int id){
    st[id/K].erase(st[id/K].find(h[id]));
}

inline void upd(int x){
    rep2(i,x*K,min((x+1)*K,n)) if(in[i]) vals[i]=max(vals[i],max(h[i]-minn[x],maxx[x]-h[i]));
    minn[x]=inf,maxx[x]=-inf;
}

inline void modifys(int x, int id){
    bug(x,id);
    if(in[x]){
        bug(x,id);
        vals[x]=max(vals[x],abs(h[x]-h[id]));
        valb[x/K]=max(valb[x/K],vals[x]);
    }
}

inline void modifyb(int x, int id){
    if(sz(st[x])) valb[x]=max(valb[x],max(h[id]-(*st[x].begin()),(*st[x].rbegin())-h[id]));
    minn[x]=min(minn[x],h[id]),maxx[x]=max(maxx[x],h[id]);
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    #ifdef i_am_noob
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    freopen("output2.txt","w",stderr);
    #endif
    cin >> n;
    rep(n) cin >> h[i] >> a[i] >> b[i];
    cin >> q;
    rep(q) cin >> qry[i].l >> qry[i].r;
    rep(q) qry[i].l--,qry[i].r--;
    rep(q) qry[i].id=i;
    sort(qry,qry+q,[&](query& i, query& j){return i.r<j.r;});
    rep(n){
        int x=i+a[i],y=i+b[i]+1;
        if(x>=n) continue;
        event tmp;
        tmp.id=i,tmp.pos=x,tmp.op=1;
        ev.pb(tmp);
        vec[i/K].pb(x);
        if(y<n){
            tmp.id=i,tmp.pos=y,tmp.op=0;
            ev.pb(tmp);
            vec[i/K].pb(y);
        }
    }
    sort(all(ev),[&](event& i, event& j){return i.pos<j.pos;});
    rep(maxn/K) sort(all(vec[i])),vec[i].resize(unique(all(vec[i]))-vec[i].begin());
    rep(maxn) vals[i]=-inf;
    rep(maxn/K+5) valb[i]=-inf,minn[i]=inf,maxx[i]=-inf;
    rep(n){
        unordered_set<int> vis;
        int tmp=cur1;
        while(cur1<sz(ev)&&ev[cur1].pos==i){
            if(ev[cur1].op) Insert(ev[cur1].id);
            else Erase(ev[cur1].id);
            vis.insert(ev[cur1].id/K);
            cur1++;
        }
        for(auto j: vis) upd(j);
        rep2(j,tmp,cur1){
            if(ev[j].op) in[ev[j].id]=1;
            else in[ev[j].id]=0;
        }
        int l=i-b[i],r=i-a[i];
        bug(i,l,r);
        rep1(j,n) if(in[j]) bug(j);
        if(l<0) l=0;
        for(; l%K&&l<=r; ++l) modifys(l,i);
        for(; l+K<=r; l+=K) modifyb(l/K,i);
        for(; l<=r; ++l) modifys(l,i);
        while(cur<q&&qry[cur].r==i){
            int res=-inf;
            l=qry[cur].l,r=qry[cur].r;
            for(; l%K&&l<=r; ++l){
                res=max(res,vals[l]);
                if(in[l]) res=max(res,max(h[l]-minn[l/K],maxx[l/K]-h[l]));
            }
            for(; l<=r; l+=K) res=max(res,valb[l/K]);
            ans[qry[cur].id]=res;
            cur++;
        }
    }
    rep(q) cout << (ans[i]<0?-1:ans[i]) << "\n";
    return 0;
}

Compilation message (stderr)

antennas.cpp: In function 'void modifys(long long int, long long int)':
antennas.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
antennas.cpp:81:5: note: in expansion of macro 'bug'
   81 |     bug(x,id);
      |     ^~~
antennas.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
antennas.cpp:83:9: note: in expansion of macro 'bug'
   83 |         bug(x,id);
      |         ^~~
antennas.cpp: In function 'int main()':
antennas.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
antennas.cpp:140:9: note: in expansion of macro 'bug'
  140 |         bug(i,l,r);
      |         ^~~
antennas.cpp:28:18: warning: statement has no effect [-Wunused-value]
   28 | #define bug(...) 826
      |                  ^~~
antennas.cpp:141:29: note: in expansion of macro 'bug'
  141 |         rep1(j,n) if(in[j]) bug(j);
      |                             ^~~

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