제출 #414946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
414946		Pro_ktmr	Two Antennas (JOI19_antennas)	C++17	100 / 100	1847 ms	41216 KiB

antennas

#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

int N;
int H[200000], A[200000], B[2000000];
int Q;
int L[200000], R[200000];
ll ans[200000];

void chmax(ll &a, ll b){
    a = max(a, b);
}

void print();

struct SegmentTree{

    int N;
    struct Node{
        int flg = 0;
        ll minLiv = 1e15L;
        ll maxAns = -1e15L;
        Node operator*(const Node &r){
            Node ret;
            ret.flg = this->flg + r.flg;
            ret.minLiv = min(this->minLiv, r.minLiv);
            ret.maxAns = max(this->maxAns, r.maxAns);
            return ret;
        }
    };
    vector<Node> node;
    struct Lazy{
        bool flg = false;
        ll H = -1e15L;
    };
    vector<Lazy> lazy;
public:
    void init(int n){
        node.clear();
        lazy.clear();
        N = 1;
        while(N < n) N = (N<<1);
        node.resize(2*N-1, Node());
        lazy.resize(2*N-1, Lazy());
    }
    void eval(int k, int l, int r){
        if(lazy[k].flg){
            chmax(node[k].maxAns, lazy[k].H - node[k].minLiv);
            if(r-l > 1){
                lazy[(k<<1)+1].flg = true;
                chmax(lazy[(k<<1)+1].H, lazy[k].H);
                lazy[(k<<1)+2].flg = true;
                chmax(lazy[(k<<1)+2].H, lazy[k].H);
            }
            lazy[k] = Lazy();
        }
    }
    void update(int a, int b, ll x, int k=0, int l=0, int r=-1){
        if(a >= b) return;
        if(r == -1) r = N;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy[k].H = x;
            lazy[k].flg = true;
            eval(k, l, r);
        }
        else{
            update(a, b, x, (k<<1)+1, l, (l+r)>>1);
            update(a, b, x, (k<<1)+2, (l+r)>>1, r);
            node[k] = node[(k<<1)+1] * node[(k<<1)+2];
        }
    }
    void build(int a, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        eval(k, l, r);
        if(r-l == 1){
            node[k].flg = 1;
            node[k].minLiv = H[l];
            while(k > 0){
                k = (k-1) >> 1;
                node[k] = node[(k<<1)+1] * node[(k<<1)+2];
            }
            return;
        }
        if(a < (l+r)/2){
            eval((k<<1)+2, (l+r)>>1, r);
            build(a, (k<<1)+1, l, (l+r)>>1);
        }
        else{
            eval((k<<1)+1, l, (l+r)>>1);
            build(a, (k<<1)+2, (l+r)>>1, r);
        }
    }
    void dest(int a, int k=0, int l=0, int r=-1){
        if(r == -1) r = N;
        eval(k, l, r);
        if(r-l == 1){
            node[k].flg = 0;
            node[k].minLiv = 1e15L;
            while(k > 0){
                k = (k-1) >> 1;
                node[k] = node[(k<<1)+1] * node[(k<<1)+2];
            }
            return;
        }
        if(a < (l+r)/2){
            eval((k<<1)+2, (l+r)>>1, r);
            dest(a, (k<<1)+1, l, (l+r)>>1);
        }
        else{
            eval((k<<1)+1, l, (l+r)>>1);
            dest(a, (k<<1)+2, (l+r)>>1, r);
        }
    }
    ll query(int a, int b, int k=0, int l=0, int r=-1){
        if(a >= b) return -1;
        if(r == -1) r = N;
        if(b <= l || r <= a) return -1;
        eval(k, l, r);
        if(a <= l && r <= b) return node[k].maxAns;
        return max(query(a, b, (k<<1)+1, l, (l+r)>>1), query(a, b, (k<<1)+2, (l+r)>>1, r));
    }
};

SegmentTree st;
priority_queue<pair<int, int>> pq;
priority_queue<pair<int, int>> ask;

void print(){
    rep(i, 2*st.N-1){
        cout << st.node[i].minLiv << " ";
    }
    cout << endl;
    rep(i, 2*st.N-1){
        cout << st.node[i].maxAns << " ";
    }
    cout << endl;
    rep(i, 2*st.N-1){
        cout << st.lazy[i].H << " ";
    }
    cout << endl;
}

signed main(){
    cin >> N;
    rep(i, N){
        cin >> H[i] >> A[i] >> B[i];
    }
    cin >> Q;
    rep(i, Q){
        cin >> L[i] >> R[i];
        L[i]--;
    }

    rep(i, Q) ans[i] = -1;
    
    rep(i, Q) ask.push({ -R[i],i });
    st.init(N);
    rep(i, N+1){
        while(!ask.empty() && -ask.top().first == i){
            int n = ask.top().second;
            ask.pop();
            chmax(ans[n], st.query(L[n], R[n]));
        }
        while(!pq.empty() && -pq.top().first == i){
            int n = pq.top().second;
            pq.pop();
            if(i == n+A[n]){
                st.build(n);
            }
            else if(i == n+B[n]+1){
                st.dest(n);
            }
        }

        if(i == N) break;

        st.update(max(0, i-B[i]), max(0,i-A[i]+1), H[i]);

        pq.push({ -(i+A[i]),i });
        pq.push({ -(i+B[i]+1),i });
    }

    rep(i, N) H[i] = 1e9L+1-H[i];
    rep(i, Q) ask.push({ -R[i],i });
    st.init(N);
    rep(i, N+1){
        while(!ask.empty() && -ask.top().first == i){
            int n = ask.top().second;
            ask.pop();
            chmax(ans[n], st.query(L[n], R[n]));
            //cout << "QUERY " << n << " = " << st.query(L[n], R[n]) << endl;
        }
        while(!pq.empty() && -pq.top().first == i){
            int n = pq.top().second;
            pq.pop();
            if(i == n+A[n]){
                st.build(n);
                //cout << "BUILD " << n << endl;
            }
            else if(i == n+B[n]+1){
                st.dest(n);
                //cout << "DESTROY " << n << endl;
            }
            //print();
        }

        if(i == N) break;

        
        st.update(max(0, i-B[i]), max(0, i-A[i]+1), H[i]);

        //cout << "UPDATE " <<  i << endl;
        //print();

        pq.push({ -(i+A[i]),i });
        pq.push({ -(i+B[i]+1),i });
    }
    
    rep(i, Q){
        cout << ans[i] << endl;
    }
}

/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5

20
260055884 2 15
737689751 5 5
575359903 1 15
341907415 14 14
162026576 9 19
55126745 10 19
95712405 11 14
416027186 8 13
370819848 11 14
629309664 4 13
822713895 5 15
390716905 13 17
577166133 8 19
195931195 10 17
377030463 14 17
968486685 11 19
963040581 4 10
566835557 1 12
586336111 6 16
385865831 8 9
1
1 20
*/

컴파일 시 표준 에러 (stderr) 메시지

antennas.cpp: In function 'void print()':
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
antennas.cpp:145:5: note: in expansion of macro 'rep'
  145 |     rep(i, 2*st.N-1){
      |     ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
antennas.cpp:149:5: note: in expansion of macro 'rep'
  149 |     rep(i, 2*st.N-1){
      |     ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
antennas.cpp:153:5: note: in expansion of macro 'rep'
  153 |     rep(i, 2*st.N-1){
      |     ^~~
antennas.cpp: In function 'int main()':
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
antennas.cpp:161:5: note: in expansion of macro 'rep'
  161 |     rep(i, N){
      |     ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
antennas.cpp:165:5: note: in expansion of macro 'rep'
  165 |     rep(i, Q){
      |     ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
antennas.cpp:170:5: note: in expansion of macro 'rep'
  170 |     rep(i, Q) ans[i] = -1;
      |     ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
antennas.cpp:172:5: note: in expansion of macro 'rep'
  172 |     rep(i, Q) ask.push({ -R[i],i });
      |     ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
antennas.cpp:174:5: note: in expansion of macro 'rep'
  174 |     rep(i, N+1){
      |     ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
antennas.cpp:199:5: note: in expansion of macro 'rep'
  199 |     rep(i, N) H[i] = 1e9L+1-H[i];
      |     ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
antennas.cpp:200:5: note: in expansion of macro 'rep'
  200 |     rep(i, Q) ask.push({ -R[i],i });
      |     ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
antennas.cpp:202:5: note: in expansion of macro 'rep'
  202 |     rep(i, N+1){
      |     ^~~
antennas.cpp:14:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   14 | #define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
      |                           ^
antennas.cpp:235:5: note: in expansion of macro 'rep'
  235 |     rep(i, Q){
      |     ^~~

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