제출 #1098647

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098647		flyingkite	Financial Report (JOI21_financial)	C++17	100 / 100	513 ms	83632 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll nxt[N], a[N], dp[N], st[N][20], tmp[N];
ll n,d;
struct segment_tree{
    ll n;
    vector<ll>st, lz;
    void init(ll _n){
        n = _n;
        st.clear(); st.resize(4 * n + 10, 0);
        lz.clear(); lz.resize(4 * n + 10, 0);
    }
    void down(ll id, ll l, ll r){
        st[id] = max(lz[id], st[id]);
        if(l != r) lz[2 * id] = max(lz[2 * id], lz[id]), lz[2 * id + 1] = max(lz[2 * id + 1], lz[id]);
        lz[id] = 0;
    }
    void update(ll id, ll l, ll r, ll left, ll right, ll val){
        down(id, l, r);
        if(l > right || r < left) return;
        if(left <= l && r <= right){
            lz[id] = max(lz[id], val);
            down(id, l, r);
            return;
        }
        ll mid = (l + r) / 2;
        update(2 * id, l, mid, left, right, val);
        update(2 * id + 1, mid + 1, r, left, right, val);
        st[id] = max(st[2 * id], st[2 * id + 1]);
    }
    ll get(ll id, ll l, ll r, ll left, ll right){
        down(id, l, r);
        if(l > right || r < left) return 0;
        if(left <= l && r <= right) return st[id];
        ll mid = (l + r) / 2;
        return max(get(2 * id, l, mid, left, right), get(2 * id + 1, mid + 1, r, left, right));
    }
    void update(ll l, ll r, ll val){update(1,1,n,l,r,val);}
    ll get(ll l, ll r){return get(1,1,n,l,r);}
} sg;
ll get(ll l, ll r){
	ll p = 31 - __builtin_clz(r - l + 1);
	return min(st[l][p], st[r - (1 << p) + 1][p]);
}
ll get_nxt(ll l, ll r){
	ll p = 31 - __builtin_clz(r - l + 1);
	return max(st[l][p], st[r - (1 << p) + 1][p]);
}
void build(){
	for(int i = 1; i <= n;i++) st[i][0] = a[i];
	for(int j = 1; j <= 19;j++){
		for(int i = 1; i + (1 << j) <= n + 1;i++) st[i][j] = min(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
	}
	for(int i = 1; i <= n;i++) tmp[i] = get(i, min(n, i + d - 1));
	for(int i = 1; i <= n;i++) st[i][0] = tmp[i];
	for(int j = 1; j <= 19;j++){
		for(int i = 1; i + (1 << j) <= n + 1;i++) st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
	}
	for(int i = 1; i + d <= n;i++){
		ll l = i + d - 1, r = n;
		while(l <= r){
			ll mid = (l + r) / 2;
			if(get_nxt(i, mid - d + 1) <= a[i]) nxt[i] = mid, l = mid + 1;
			else r = mid - 1;
		}
		nxt[i] = min(n, nxt[i] + 1);
	}
	for(int i = 1; i <= n;i++) if(i + d > n) nxt[i] = n;
}
void to_thic_cau(){
	cin >> n >> d;
	vector<pll>v;
	for(int i = 1; i <= n;i++){
		cin >> a[i];
		v.pb({a[i], i});
	}
	build();
	sort(all(v));
	sg.init(n);
	ll res = 0;
	for(int i = 0; i < v.size();i++){
		ll j = i;
		while(j < v.size() && v[j].F == v[i].F){
			ll idx = v[j].S;
			dp[idx] = max(1ll, sg.get(idx, idx) + 1);
			res = max(res, dp[idx]);
			j++;
		}
		for(int k = i; k < j;k++){
			ll idx = v[k].S;
			sg.update(idx, nxt[idx], dp[idx]);			
		}
		i = j - 1;
	}
	cout << res << '\n';
}
 
signed main()   
{ 
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

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

Main.cpp: In function 'void to_thic_cau()':
Main.cpp:93:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i = 0; i < v.size();i++){
      |                 ~~^~~~~~~~~~
Main.cpp:95:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   while(j < v.size() && v[j].F == v[i].F){
      |         ~~^~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 35 / 35