제출 #203939

#제출 시각아이디문제언어결과실행 시간메모리
203939RakhmandTwo Antennas (JOI19_antennas)C++14
0 / 100
469 ms31864 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 = 1e9 + 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); } } int n, Q, mx[MXN * 4], d[MXN * 4], mod[MXN * 4], ans[MXN]; pair<int, int> q[MXN]; vector<int> st[MXN], en[MXN]; vector<int> ranges[MXN]; struct antenna{ int a, b, h; }a[MXN]; void clearTree(){ for(int i = 1; i < MXN * 4; i++){ d[i] = -1; mx[i] = 0; mod[i] = OO; } } void push(int v){ if(mod[v] != OO){ mod[v + v] = min(mod[v + v], mod[v]); mod[v + v + 1] = min(mod[v + v + 1], mod[v]); } d[v] = max(d[v], mx[v] - mod[v]); mod[v] = OO; } void updating(int v){ mx[v] = max(mx[v + v], mx[v + 1 + v]); d[v] = max(d[v + v], d[v + v + 1]); } void upd(int v, int tl, int tr, int pos, int x){ push(v); if(tl == tr){ mx[v] = x; return ; } int 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(int v, int tl, int tr, int l, int r, int x){ push(v); if(l <= tl && tr <= r){ mod[v] = x; push(v); return ; } if(r < tl || tr < l){ return ; } int tm = (tl + tr) / 2; segupd(v + v, tl, tm, l, r, x); segupd(v + v + 1, tm + 1, tr, l, r, x); updating(v); } int get(int v, int tl, int tr, int l, int r){ push(v); if(l <= tl && tr <= r){ return d[v]; } if(r < tl || tr < l){ return -1; } int tm = (tl + tr) / 2; return max(get(v + v, tl, tm, l, r), get(v + v + 1, tm + 1, tr, l, r)); } void solve(){ clearTree(); for(int i = 1; i <= n; i++){ ranges[i].clear(); st[i].clear(); en[i].clear(); } for(int i = 1; i <= Q; i++){ ranges[q[i].S].push_back(i); } for(int i = 1; i <= n; i++){ if(i + a[i].a <= n){ st[i + a[i].a].push_back(i); } if(i + a[i].b <= n){ en[i + a[i].b].push_back(i); } for(auto it : st[i]){ upd(1, 1, n, it, a[it].h); } if(i - a[i].a > 0){ int right = i - a[i].a, left = max(1, i - a[i].b); segupd(1, 1, n, left, right, a[i].h); } for(auto i : ranges[i]){ ans[i] = max(get(1, 1, n, q[i].F, q[i].S), ans[i]); } for(auto it : en[i]){ upd(1, 1, n, it, 0); } } } int main () { ios; //gettxt(0); cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i].h >> a[i].a >> a[i].b; } cin >> Q; for(int i = 1; i <= Q; i++){ ans[i] = -1; cin >> q[i].F >> q[i].S; } solve(); reverse(a + 1, a + n + 1); for(int i = 1; i <= Q; i++){ q[i] = {n - q[i].S + 1, n - q[i].F + 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...