oj.uz

Submission #502368

# Submission time Handle Problem Language Result Execution time Memory
502368 2022-01-05T20:27:21 Z AmirElarbi Akcija (COCI21_akcija) C++14
10 / 110
 10 ms 15328 KB 
#include <bits/stdc++.h>
//#include "bubblesort2.h"
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e7
#define eps 1e-4
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
const int MOD = 1e9+7;
const int nax = 2005;
struct node {
    int mn = 0, pos = 0, prop = 0;
    node () {}
    node (int _mn, int _pos, int _prop) {
        mn = _mn; pos = _pos; prop = _prop;
    }
};
struct sgtree{
	node st[4*nax];
	node merge(node x, node y){
		if(x.mn >= y.mn) return y; else return x;
	}
	void init(int v, int l, int r){
		if(l==r){
			st[v].mn = st[v].pos = l+1;
			st[v].prop = 0;
			return ;
		}
		int md = (l+r)/2;
		init(v*2,l,md);
		init(v*2+1,md+1,r);
		st[v] = merge(st[v*2],st[v*2+1]);
	}
	void propagate (int x) {
        if (st[x].prop == 0) return;

        if (x < 2*nax) {
            st[2 * x].prop += st[x].prop;
            st[2 * x + 1].prop += st[x].prop;
        }

        st[x].mn += st[x].prop;
        st[x].prop = 0;
    }
    void update(int v,int l, int r, int i, int j, int val){
    	propagate(v);
    	if(r < i || l > j) return;
    	if(l >= i && r <= j){
    		st[v].prop += val;
    		propagate(v);
    		return;
    	}
    	int md = (l+r)/2;
    	update(v*2, l,md,i,j,val);
    	update(v*2+1,md+1,r,i,j,val);
    	st[v] = merge(st[v*2],st[v*2+1]);
    }

    node query(int v,int l, int r, int i, int j){
    	propagate(v);
    	//cout << l << " " << r << endl;
    	if(r < i || l > j) {
    		node INF_N(INF,0,0);
    		return INF_N;
    	}
    	if(l >= i && r <= j){
    		//cout << st[v].mn << "  " << l << " " << r  << endl;
    		return st[v];
    	}
    	int md = (l+r)/2;
    	return st[v] = merge(query(v*2, l,md,i,j),query(v*2+1,md+1,r,i,j));
    }

} t;
 int n,k;
int cnt = 0;
ve<pair<int,ll>> s;
short opt[nax][nax], stat[nax][nax];
priority_queue<pair<pair<int,ll>, pair<int,int> >> pq;
pair<int,ll> cal(){
	int b = 0;
	ll sum = 0;
	t.init(1,0,n-1);
	for (int i = 0; i < n; ++i)
	{
		opt[cnt][i] = 0;
		if(stat[cnt][i] == 1 || (stat[cnt][i] == 0 && t.query(1,0,n-1,s[i].fi-1,n-1).mn>0)){
			opt[cnt][i] = 1;
			b++,sum+=s[i].se;
			t.update(1,0,n-1,s[i].fi-1,n-1,-1);
		}
	}
	return {b,sum};
}
void bfs(pair<int,ll> cur){
	ve<ll> bst(n);
	for (int i = 0; i < n; ++i)
	{
		bst[i] = INF;
	}
	for (int i = 0; i < n; ++i)
	{
		if(stat[cnt][i] == 0 && opt[cnt][i] == 0){
			bst[i] = s[i].se;
		} 
	}
	for (int i = n-2; i >= 0; --i)
	{
		bst[i] = min(bst[i],bst[i+1]);
	}
	for (int i = 0; i < n; ++i)
	{
		if(stat[cnt][i] == 0 && opt[cnt][i] == 1){
			int rmi = t.query(1,0,n-1,0,s[i].fi-1).pos-1;
			int a = 0;
			ll b = 0;
			if(bst[rmi+1] == INF){
				a = cur.fi-1;
				b = cur.se-s[i].se;
			} else {
				a = cur.fi,
				b = cur.se-s[i].se+bst[rmi+1]; 
			}
			pq.push({{a,-b},{cnt,i}});
		}
	}
}
void qpop(){
	pair<int,ll> a= pq.top().fi;
	pair<int,int> b = pq.top().se;
	pq.pop();
	cout << a.fi << " " << -a.se << endl;
	if(a.fi == -1) return ;
	for (int i = 0; i < n; ++i)
	{
		stat[cnt][i] = stat[b.fi][i];
		if(stat[b.fi][i] == 0 && opt[b.fi][i] == 1){
			if(i<b.se)stat[cnt][i] = 1;
			else if(i == b.se) stat[cnt][i] = -1;
			else stat[cnt][i] = 0;
		}
	}
}
int main(){
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
    {
    	int a,b;
    	cin >> a >> b;
    	s.pb({b,a});
    }
    sort(s.begin(), s.end());
    pair<int,ll> best = cal();
    pq.push({{best.fi,-best.se},{-1,-1}});
    while(cnt < k){
    	cnt++;
    	qpop();
    	bfs(cal());
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Incorrect 3 ms 460 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 15328 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 460 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Incorrect 3 ms 460 KB Output isn't correct
15 Halted 0 ms 0 KB -