제출 #1200585

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200585		nguyn	Financial Report (JOI21_financial)	C++20	0 / 100	31 ms	9272 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define F first
#define S second
#define pb push_back 
#define pii pair<int,int>

const int N = 3e5 + 5;

struct SegTree {
	int n;
	vector<int> st;

	SegTree() {}
	SegTree(int n) : n(n) {
		st.resize(4 * n + 5); 
	}

	void update(int id, int l, int r, int i, int x) {
		if (l == r) {
			st[id] = x;
			return; 
		}
		int mid = (l + r) / 2;
		if (mid >= i) update(id * 2, l, mid, i, x);
		else update(id * 2 + 1, mid + 1, r, i, x); 
		st[id] = max(st[id * 2], st[id * 2 + 1]); 
	}

	int get(int id, int l, int r, int u, int v) {
		if (u <= l && r <= v) {
			return st[id]; 
		} 
		int mid = (l + r) / 2; 
		if (u > mid) return get(id * 2 + 1, mid + 1, r, u, v); 
		if (mid >= v) return get(id * 2, l, mid, u, v); 
		return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));  
	}
};

int a[N], n, d;
int last[N];
int mn[N]; 
int cur[N];
vector<int> compressed;

signed main(){
    ios_base::sync_with_stdio(false) ; 
    cin.tie(0) ; cout.tie(0) ; 
    if (fopen("INP.INP" ,"r")) {
        freopen("INP.INP" ,"r" , stdin) ;
        freopen("OUT.OUT" , "w" , stdout) ;
    }
    cin >> n >> d; 
    for (int i = 1; i <= n; i++) {
    	cin >> a[i]; 
    	compressed.pb(a[i]);
    }
    sort(compressed.begin(), compressed.end()); 
    compressed.erase(unique(compressed.begin(), compressed.end()), compressed.end()); 
    for (int i = 1; i <= n; i++) {
    	a[i] = upper_bound(compressed.begin(), compressed.end(), a[i]) - compressed.begin();
    }
    deque<int> dq;
    for (int i = 1; i <= n; i++) {
    	while(!dq.empty() && dq.front() <= i - d) dq.pop_front(); 
    	while(!dq.empty() && a[i] <= a[dq.back()]) dq.pop_back(); 
    	dq.push_back(i); 
    	mn[i] = a[dq.front()]; 
    }
    int sz = compressed.size(); 
    SegTree seg(sz); 
    for (int i = 1; i <= n; i++) {
    	last[i] = seg.get(1, 1, sz, a[i] + 1, n) + 1;
    	seg.update(1, 1, sz, mn[i], i); 
    }
    seg = SegTree(sz); 
    int res = 0;
    priority_queue<pii> pq; 
    for (int i = n; i >= 1; i--) {
    	while(!pq.empty()) {
    		if (pq.top().F <= i + d) break; 
    		if (cur[pq.top().S] > i + d) seg.update(1, 1, sz, pq.top().S, 0); 
    	}
    	int f = seg.get(1, 1, sz, a[i] + 1, sz); 
    	res = max(res, f); 
    	cur[a[i]] = min(cur[a[i]], last[i]);
    	pq.push({cur[a[i]], a[i]}); 
    	seg.update(1, 1, sz, a[i], f + 1); 
    }
    cout << res;
}

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

Main.cpp: In function 'int main()':
Main.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen("INP.INP" ,"r" , stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("OUT.OUT" , "w" , stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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