제출 #934055

#제출 시각아이디문제언어결과실행 시간메모리
934055vjudge1Bridges (APIO19_bridges)C++98
16 / 100
456 ms1616 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; int arr[50001]; struct ST{ int tree[200001]; void build(int node, int l, int r){ if(l==r){ tree[node]=arr[l]; return; } build(2*node+1, l, (l+r)/2); build(2*node+2, (l+r)/2+1, r); tree[node]=min(tree[2*node+1], tree[2*node+2]); } void update(int node, int l, int r, int pos, int x){ if(r<pos || l>pos) return; if(l==r){ tree[node]=x; return; } update(2*node+1, l, (l+r)/2, pos, x); update(2*node+2, (l+r)/2+1, r, pos, x); tree[node]=min(tree[2*node+1], tree[2*node+2]); } int query(int node, int l, int r, int a, int b){ if(l>b || r<a) return (1<<30); if(l>=a && r<=b){ return tree[node]; } return min(query(2*node+1, l, (l+r)/2, a, b), query(2*node+2, (l+r)/2+1, r, a, b)); } }; int n, m, q; ST tree; int buscaizq(int l, int r, int pos, int x){ int mid; while(l<r){ mid=(l+r+1)/2; if(pos-mid>=0 && tree.query(0, 0, n-1, pos-mid, pos-1)>=x) l=mid; else r=mid-1; } return l; } int buscadere(int l, int r, int pos, int x){ int mid; while(l<r){ mid=(l+r+1)/2; if(pos+mid<n && tree.query(0, 0, n-1, pos+1, pos+mid)>=x) l=mid; else r=mid-1; } return l; } void solve(){ cin>> n>> m; int t, a, b, c, x, y; for(int i=0; i<m; i++){ cin>> a>> b>> c; arr[i]=c; } tree.build(0, 0, n-1); cin>> q; for(int i=0; i<q; i++){ cin>> t>> a>> b; a--; if(t==1){ tree.update(0, 0, n-1, a, b); } else{ x=buscaizq(0, n-1, a, b); y=buscadere(0, n-1, a-1, b); cout<< x+y+1<< "\n"; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin.tie(0); int t=1; //cin>> t; while(t--){ solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...