제출 #204095

#제출 시각아이디문제언어결과실행 시간메모리
204095RakhmandTwo Antennas (JOI19_antennas)C++14
0 / 100
31 ms33272 KiB
// // ROIGold.cpp // Main calisma // // Created by Rakhman on 05/02/2019. // Copyright © 2019 Rakhman. All rights reserved. // #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <queue> #include <cmath> #include <cstdlib> #include <ctime> #include <cassert> #include <iterator> #define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0); #define S second #define F first #define pb push_back #define nl '\n' #define NL cout << '\n'; #define EX exit(0) #define all(s) s.begin(), s.end() #define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k) const long long MXN = 2e5 + 200; const long long N = 2e5 + 200; const long long MNN = 5e3 + 100; const long long MOD = 1e9 + 7; const long long INF = 1e18; const long long OO = 2e9 + 500; typedef long long llong; typedef unsigned long long ullong; using namespace std; void gettxt(bool yes){ if(yes == 1){ freopen("problem.in", "r", stdin); freopen("problem.out", "w", stdout); }else{ freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin); } } llong n, Q, ans[MXN], ql[MXN], qr[MXN]; vector<llong> st[MXN], en[MXN], range[MXN]; struct antenna{ llong a, b, h; }b[MXN]; struct node{ llong t, mx, mod; }t[MXN * 4]; void push(llong v, llong tl, llong tr){ if(t[v].mod == OO) return ; if(tl != tr){ t[v + v].mod = min(t[v + v].mod, t[v].mod); t[v + v + 1].mod = min(t[v + v + 1].mod, t[v].mod); } t[v].t = max(t[v].t, t[v].mx - t[v].mod); t[v].mod = OO; } void updating(llong v){ t[v].mx = max(t[v + v].mx, t[v + v + 1].mx); t[v].t = max(t[v + v].t, t[v + v + 1].t); } void upd(llong v, llong tl, llong tr, llong pos, llong x){ push(v, tl, tr); if(tl == tr){ t[v].mx = x; return ; } llong tm = (tl + tr) / 2; if(pos <= tm){ upd(v + v, tl, tm, pos, x); }else{ upd(v + v + 1, tm + 1, tr, pos, x); } updating(v); } void segupd(llong v, llong tl, llong tr, llong l, llong r, llong x){ push(v, tl, tr); if(l <= tl && tr <= r){ t[v].mod = min(t[v].mod, x); push(v, tl, tr); return ; } if(r < tl || tr < l) return ; llong tm = (tl + tr) / 2; segupd(v + v, tl, tm, l, r, x); segupd(v + v + 1, tm + 1, tr, l, r, x); updating(v); } llong get (int v, int tl, int tr, int l, int r) { push(v, tl, tr); if (tl >= l && tr <= r) return t[v].t; if (tl > r || l > tr) return -1; int tm = (tl + tr) >> 1; return max(get (v + v, tl, tm, l, r), get(v + v + 1, tm + 1, tr, l, r)); } void solve(){ for(llong i = 1; i < MXN * 4; i++){ t[i].t = -1; t[i].mx = 0; t[i].mod = OO; } for (int i = 1; i <= n; i ++) { st[i].clear(); en[i].clear(); range[i].clear(); } for (int i = 1; i <= Q; i ++) { range[qr[i]].pb(i); } for (int i = 1; i <= n; i ++) { if (i + b[i].a <= n) { st[i + b[i].a].pb(i); } if (i + b[i].b <= n) { en[i + b[i].b].pb(i); } } for(int i = 1; i <= n; i++){ for (auto j : st[i]) upd(1, 1, n, j, b[j].h); if (i > b[i].a) { segupd(1, 1, n, i - b[i].b, i - b[i].a, b[i].h); } for (auto j : range[i]) { ans[j] = max(ans[j], get(1, 1, n, ql[j], qr[j])); } for (auto j : en[i]) upd(1, 1, n, j, 0); } } int main () { ios; gettxt(0); cin >> n; for (int i = 1; i <= n; i ++) { cin >> b[i].h >> b[i].a >> b[i].b; } cin >> Q; for (int i = 1; i <= Q; ++i) { ans[i] = -1; cin >> ql[i] >> qr[i]; } solve(); reverse(b + 1, b + n + 1); for (int i = 1; i <= Q; i ++) { tie(ql[i], qr[i]) = make_pair(n - qr[i] + 1, n - ql[i] + 1); } solve(); for (int i = 1; i <= Q; i ++) cout << ans[i] << nl; return 0; }

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

antennas.cpp: In function 'void gettxt(bool)':
antennas.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("problem.in", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("problem.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...