oj.uz

답안 #861044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
861044 2023-10-15T07:52:10 Z guagua0407 Two Antennas (JOI19_antennas) C++17
24 / 100
 3000 ms 114516 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

const int mxn=200005;
multiset<ll> segtree[mxn*4];
ll h[mxn],a[mxn],b[mxn];
int n,q;
ll val;

void update(int pos,int l=1,int r=n,int v=1){
    if(l>r) return;
    segtree[v].insert(h[pos]);
    if(l==r) return;
    int mid=(l+r)/2;
    if(pos<=mid) update(pos,l,mid,v*2);
    else update(pos,mid+1,r,v*2+1);
}

void erase(int pos,int l=1,int r=n,int v=1){
    if(l>r) return;
    segtree[v].erase(segtree[v].find(h[pos]));
    if(l==r) return;
    int mid=(l+r)/2;
    if(pos<=mid) erase(pos,l,mid,v*2);
    else erase(pos,mid+1,r,v*2+1);
}

ll mnquery(int tl,int tr,int l=1,int r=n,int v=1){
    if(r<tl or tr<l){
        return 2e9;
    }
    if(tl<=l and r<=tr){
        return (segtree[v].empty()?(2e9):*segtree[v].begin());
    }
    int mid=(l+r)/2;
    return min(mnquery(tl,min(mid,tr),l,mid,v*2),mnquery(max(tl,mid+1),tr,mid+1,r,v*2+1));
}

ll mxquery(int tl,int tr,int l=1,int r=n,int v=1){
    if(r<tl or tr<l){
        return -2e9;
    }
    if(tl<=l and r<=tr){
        return (segtree[v].empty()?(-2e9):*segtree[v].rbegin());
    }
    int mid=(l+r)/2;
    return max(mxquery(tl,min(mid,tr),l,mid,v*2),mxquery(max(tl,mid+1),tr,mid+1,r,v*2+1));
}


int main() {_
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i]>>a[i]>>b[i];
    }
    cin>>q;
    for(int i=0;i<q;i++){
        for(int j=0;j<mxn*4;j++){
            segtree[j].clear();
        }
        ll l,r;
        cin>>l>>r;
        vector<int> st[mxn],en[mxn];
        for(int j=l;j<=r;j++){
            if(j-b[j]+1>r or j-a[j]+1<l) continue;
            //cout<<max(l,j-b[j])<<' '<<min(r,j-a[j])+1<<'\n';
            st[max(l,j-b[j])].push_back(j);
            en[min(r,j-a[j])+1].push_back(j);
        }
        ll ans=-1;
        for(int j=l;j<=r;j++){
            for(auto v:st[j]){
                update(v);
            }
            for(auto v:en[j]){
                erase(v);
            }
            ll L=j+a[j];
            ll R=j+b[j];
            if(L>r or R<l) continue;
            L=max(L,l);
            R=min(R,r);
            val=h[j];
            if(mnquery(L,R)!=2e9) ans=max(ans,abs(h[j]-mnquery(L,R)));
            if(mxquery(L,R)!=-2e9) ans=max(ans,abs(h[j]-mxquery(L,R)));
        }
        cout<<(ans>1e9?-1:ans)<<'\n';
    }
    return 0;
}
//maybe its multiset not set

Compilation message

antennas.cpp: In function 'void setIO(std::string)':
antennas.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 52056 KB Output is correct
2 Correct 726 ms 51956 KB Output is correct
3 Correct 1146 ms 51952 KB Output is correct
4 Correct 1161 ms 51960 KB Output is correct
5 Correct 470 ms 51800 KB Output is correct
6 Correct 532 ms 51964 KB Output is correct
7 Correct 1139 ms 52048 KB Output is correct
8 Correct 1134 ms 52196 KB Output is correct
9 Correct 1106 ms 52052 KB Output is correct
10 Correct 911 ms 52208 KB Output is correct
11 Correct 1133 ms 51920 KB Output is correct
12 Correct 1141 ms 52460 KB Output is correct
13 Correct 584 ms 51804 KB Output is correct
14 Correct 1159 ms 51944 KB Output is correct
15 Correct 696 ms 51804 KB Output is correct
16 Correct 1168 ms 51936 KB Output is correct
17 Correct 816 ms 52184 KB Output is correct
18 Correct 1138 ms 52052 KB Output is correct
19 Correct 84 ms 51940 KB Output is correct
20 Correct 1150 ms 52176 KB Output is correct
21 Correct 1068 ms 52204 KB Output is correct
22 Correct 1158 ms 51956 KB Output is correct
23 Correct 1012 ms 51964 KB Output is correct
24 Correct 1136 ms 51932 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 52056 KB Output is correct
2 Correct 726 ms 51956 KB Output is correct
3 Correct 1146 ms 51952 KB Output is correct
4 Correct 1161 ms 51960 KB Output is correct
5 Correct 470 ms 51800 KB Output is correct
6 Correct 532 ms 51964 KB Output is correct
7 Correct 1139 ms 52048 KB Output is correct
8 Correct 1134 ms 52196 KB Output is correct
9 Correct 1106 ms 52052 KB Output is correct
10 Correct 911 ms 52208 KB Output is correct
11 Correct 1133 ms 51920 KB Output is correct
12 Correct 1141 ms 52460 KB Output is correct
13 Correct 584 ms 51804 KB Output is correct
14 Correct 1159 ms 51944 KB Output is correct
15 Correct 696 ms 51804 KB Output is correct
16 Correct 1168 ms 51936 KB Output is correct
17 Correct 816 ms 52184 KB Output is correct
18 Correct 1138 ms 52052 KB Output is correct
19 Correct 84 ms 51940 KB Output is correct
20 Correct 1150 ms 52176 KB Output is correct
21 Correct 1068 ms 52204 KB Output is correct
22 Correct 1158 ms 51956 KB Output is correct
23 Correct 1012 ms 51964 KB Output is correct
24 Correct 1136 ms 51932 KB Output is correct
25 Execution timed out 3026 ms 52060 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1149 ms 97288 KB Output is correct
2 Correct 1307 ms 104144 KB Output is correct
3 Correct 827 ms 87984 KB Output is correct
4 Correct 1335 ms 104344 KB Output is correct
5 Correct 395 ms 74660 KB Output is correct
6 Correct 1365 ms 104348 KB Output is correct
7 Correct 1103 ms 97056 KB Output is correct
8 Correct 1387 ms 104172 KB Output is correct
9 Correct 84 ms 59472 KB Output is correct
10 Correct 1311 ms 104400 KB Output is correct
11 Correct 654 ms 83448 KB Output is correct
12 Correct 1338 ms 103996 KB Output is correct
13 Correct 525 ms 106704 KB Output is correct
14 Correct 489 ms 105416 KB Output is correct
15 Correct 381 ms 97232 KB Output is correct
16 Correct 470 ms 114516 KB Output is correct
17 Correct 559 ms 111056 KB Output is correct
18 Correct 479 ms 94968 KB Output is correct
19 Correct 418 ms 81544 KB Output is correct
20 Correct 424 ms 87888 KB Output is correct
21 Correct 448 ms 97232 KB Output is correct
22 Correct 476 ms 97996 KB Output is correct
23 Correct 455 ms 90788 KB Output is correct
24 Correct 396 ms 100164 KB Output is correct

Subtask #4
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 265 ms 52056 KB Output is correct
2 Correct 726 ms 51956 KB Output is correct
3 Correct 1146 ms 51952 KB Output is correct
4 Correct 1161 ms 51960 KB Output is correct
5 Correct 470 ms 51800 KB Output is correct
6 Correct 532 ms 51964 KB Output is correct
7 Correct 1139 ms 52048 KB Output is correct
8 Correct 1134 ms 52196 KB Output is correct
9 Correct 1106 ms 52052 KB Output is correct
10 Correct 911 ms 52208 KB Output is correct
11 Correct 1133 ms 51920 KB Output is correct
12 Correct 1141 ms 52460 KB Output is correct
13 Correct 584 ms 51804 KB Output is correct
14 Correct 1159 ms 51944 KB Output is correct
15 Correct 696 ms 51804 KB Output is correct
16 Correct 1168 ms 51936 KB Output is correct
17 Correct 816 ms 52184 KB Output is correct
18 Correct 1138 ms 52052 KB Output is correct
19 Correct 84 ms 51940 KB Output is correct
20 Correct 1150 ms 52176 KB Output is correct
21 Correct 1068 ms 52204 KB Output is correct
22 Correct 1158 ms 51956 KB Output is correct
23 Correct 1012 ms 51964 KB Output is correct
24 Correct 1136 ms 51932 KB Output is correct
25 Execution timed out 3026 ms 52060 KB Time limit exceeded
26 Halted 0 ms 0 KB -