제출 #1031118

#제출 시각아이디문제언어결과실행 시간메모리
1031118hasan2006Election (BOI18_election)C++17
0 / 100
2 ms6748 KiB
#include <bits/stdc++.h> using namespace std; #define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define rall(s) s.rbegin(),s.rend() #define all(s) s.begin(),s.end() #define pb push_back #define se second #define fi first #define ll long long #define ld long double #define YES cout<<"YES\n" #define Yes cout<<"Yes\n" #define yes cout<<"yes\n" #define NO cout<<"NO\n" #define No cout<<"No\n" #define no cout<<"no\n" const int N = 1e6 + 9 , mod = 1e9 + 7; ll a[N] , b[N] , dp[N] , c[N] , d[N] , t[N * 3] , lz[N * 3]; void pushup(int i){ t[i] = min(t[2 * i] , t[2 * i + 1]); } void pushlazy(int i){ t[2 * i] += lz[i] , t[2 * i + 1] += lz[i]; lz[2 * i + 1] += lz[i] , lz[2 * i] += lz[i]; lz[i] = 0; } void add(int i , int l , int r , int tl , int tr , int x){ int m = (l + r) / 2; if(l > tr || r < tl) return; if(l >= tl && r <= tr){ t[i] += x , lz[i] += x; }else { pushlazy(i); add(2 * i , l , m , tl , tr , x); add(2 * i + 1 , m + 1 , r , tl , tr , x); pushup(i); } } ll get(int i , int l , int r , int tl , int tr){ int m = (l + r) / 2; if(l > tr || r < tl) return 1e18; if(l >= tl && r <= tr){ return t[i]; }else { pushlazy(i); return min(get(2 * i , l , m , tl , tr) , get(2 * i + 1 , m + 1 , r , tl , tr)); } } void solve() { ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ; cin>>n; for(i = 1; i <= n; i++){ char ch; cin>>ch; a[i] = (ch == 'T' ? -1 : 1); b[i] = b[i - 1] + a[i]; add(1 , 1 , n, i , i, b[i]); } cin>>q; vector<pair<int,pair<int,int>>>v; for(i = 1; i <= q; i++) cin>>l>>r , v.pb({r , {l , i}}); sort(all(v)); deque<int>d; k = 1; for(auto to : v){ l = to.se.fi , r = to.fi; while(k <= r){ if(a[k] == -1) add(1 , 1 , n , k , n , 1) , d.push_back(k); else if(d.size()) add(1 , 1 , n , d.back() , n , -1) , d.pop_back(); k++; } ll L = 0 , R = d.size() , M; if(d.size()){ while(L != R){ M = (L + R) / 2; if(d[M] >= l) R = M; else L = M + 1; } } c[to.se.se] = (d.size() - L) + max(b[l - 1] - get(1 , 1 , n , l , r) , 0ll); } /* for(i = 0; i <= 2e6; i++) t[i] = 0 , lz[i] = 0; reverse(a + 1 , a + n + 1); for(i = 1; i <= n; i++) b[i] = b[i - 1] + a[i] , add(1 , 1 , n , i , i , b[i]); for(i = 0; i < v.size(); i++){ v[i].fi = n - v[i].fi + 1; v[i].se.fi = n - v[i].se.fi + 1; swap(v[i].fi , v[i].se.fi); } sort(all(v)); d.clear(); k = 1; for(auto to : v){ l = to.se.fi , r = to.fi; while(k <= r){ if(a[k] == -1) add(1 , 1 , n , k , n , 1) , d.push_back(k); else if(d.size()) add(1 , 1 , n , d.back() , n , -1) , d.pop_back(); k++; } f = d.size(); c[to.se.se] = f + max(b[l - 1] - get(1 , 1 , n , l , r) , 0ll); }*/ for(i =1; i <= q;i ++) cout<<c[i]<<"\n"; } int main(){ TL; /*#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif*/ int t = 1; //cin>>t; while(t--) { solve(); } } // Author : حسن

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

election.cpp: In function 'void solve()':
election.cpp:60:20: warning: unused variable 'j' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                    ^
election.cpp:60:30: warning: unused variable 'x' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                              ^
election.cpp:60:34: warning: unused variable 'y' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                  ^
election.cpp:60:38: warning: unused variable 's' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                      ^
election.cpp:60:46: warning: unused variable 'f' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                              ^
election.cpp:60:54: warning: unused variable 'm' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                      ^
election.cpp:60:58: warning: unused variable 'mn' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                          ^~
election.cpp:60:69: warning: unused variable 'mx' [-Wunused-variable]
   60 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                                     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...