제출 #1163584

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163584		Ruichen	Akcija (COCI21_akcija)	C++20	30 / 110	1 ms	584 KiB

Main

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

struct gift{
	int v, t;
	const bool operator<(const gift &e) const{if(t==e.t){return v<e.v;}return t<e.t;}
};

struct node{
	int S, E, M, val=1, in=0, sum=0;
	node *left, *right;
	node(int s, int e): S(s), E(e){
		if(S==E){
			val=0;
			sum=0;
			in=S;
			return;
		}
		M=S+(E-S)/2;
		left=new node(S,M);
		right=new node(M+1,E);
		if(left->val>right->val){
			in=left->in;
			val=left->val;
		}
		else{
			in=right->in;
			val=right->val;
		}
		sum=left->sum+right->sum;
	}
	void upd(int m, int x){
		if(S==E){
			val=x;
			sum=x;
			return;
		}
		if(m<=M){
			left->upd(m,x);
		}
		else{
			right->upd(m,x);
		}
		if(left->val>right->val){
			in=left->in;
			val=left->val;
		}
		else{
			in=right->in;
			val=right->val;
		}
		sum=left->sum+right->sum;
	}
	pair<int,int> qry(int l, int r){
		if(S>r||E<l){
			return {0,-1};
		}
		if(l<=S&&E<=r){
			return {val,in};
		}
		int v1, v2, i1, i2;
		tie(v1,i1)=left->qry(l,r);
		tie(v2,i2)=right->qry(l,r);
		if(v1>v2){
			return {v1,i1};
		}
		return {v2,i2};
	}
	int qrysum(int l, int r){
		if(S>r||E<l){
			return 0;
		}
		if(l<=S&&E<=r){
			return sum;
		}
		return left->qrysum(l,r)+right->qrysum(l,r);
	}
}*segtree;

signed main(){
	int n, k, s=0, p=0;
	cin >> n >> k;
	vector<gift> a(n);
	for(int i=0; i<n; i++){
		cin >> a[i].v >> a[i].t;
	}
	sort(a.begin(),a.end());
	segtree=new node(0,n-1);
	int mv, in;
	for(int i=0; i<n; i++){
		s=a[i].t;
		if(s==p&&s>0){
			tie(mv,in)=segtree->qry(0,p);
			if(a[i].v<mv){
				segtree->upd(in,a[i].v);
			}
		}
		else if(p<s){
			segtree->upd(p,a[i].v);
			p++;
		}
	}
	cout << p << " " << segtree->qrysum(0,n-1) << endl;
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 30
• Subtask 6: 0 / 20