oj.uz

Submission #893902

# Submission time Handle Problem Language Result Execution time Memory
893902 2023-12-27T16:50:50 Z vjudge1 Meteors (POI11_met) C++14
100 / 100
 1582 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

#define PII       pair<int,int>
#define all(c)    c.begin(),c.end()
#define sz(c)     (int)c.size()
#define clr(c)    c.clear()
#define pb        push_back
#define mp        make_pair
#define cin(x)    scanf("%d",&x)
#define MOD		1000000007
#define EPS		1E-10

const LL maxval = MOD;
const int maxn = 300005;
vector<int> owner[maxn];
LL reqd[maxn];
int ql[maxn],qr[maxn];
LL qa[maxn];
int lo[maxn], hi[maxn];
vector<int> tocheck[maxn];

long long tree[maxn];
int n,m;
int k;
long long maxi=0;
void update(int x, long long val){
	while(x<=m){
		tree[x]+=val;
		//[x]=min(tree[x],maxi);
		x+=(x&-x);
		
	}
}
long long read(int x){
	long long s=0;
	while(x>0){
		s+=tree[x];
		//s=min(tree[x],maxi);
		x-=(x&-x);
	}
	return s;
}

void apply(int x){
	if(ql[x]<=qr[x])
		update(ql[x],qa[x]),update(qr[x]+1,-qa[x]);
	else{
		update(1,qa[x]);
		update(qr[x]+1,-qa[x]);
		update(ql[x],qa[x]);
	}
}

int main()
{
	cin(n);
	cin(m);
	for(int i = 1; i <= m; i++)
	{
		int x;
		cin(x);
		owner[x].pb(i);
	}
	for(int i = 1; i <= n; i++)
		scanf("%lld",&reqd[i]);
	cin(k);
	for(int i = 1; i <= k; i++)
	{
		cin(ql[i]);
		cin(qr[i]);
		scanf("%lld",&qa[i]);
	}
	for(int i = 1; i <= n; i++)
	{
		lo[i] = 1;
		hi[i] = k + 1;
	}
	bool changed = true;
	while(changed)
	{
		changed = false;

		// clean up mess.
		for(int a = 0; a <= m; a++)
			tree[a] = 0;
		for(int i = 1; i <= n; i++)
			if(lo[i] != hi[i])
				tocheck[ (lo[i] + hi[i]) >> 1 ].pb(i);
		// end of cleaning up

		for(int q = 1; q <= k; q++)
		{
			apply(q);

			while(sz(tocheck[q]))
			{
				changed = true;
				int id = tocheck[q].back();
				tocheck[q].pop_back();

				LL sum = 0;
				for(auto sectors: owner[id])
				{
					sum += read(sectors);
					if(sum >= reqd[id]) break;
				}
				if(sum >= reqd[id])
					hi[id] = q;
				else
					lo[id] = q + 1;
			}
		}
	}
	for(int i = 1; i <= n; i++)
	{
		assert(lo[i] == hi[i]);		
		if(lo[i] <= k)
			printf("%d\n",lo[i]);
		else
			printf("NIE\n");
	}
	return 0;
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:12:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define cin(x)    scanf("%d",&x)
      |                   ~~~~~^~~~~~~~~
met.cpp:59:2: note: in expansion of macro 'cin'
   59 |  cin(n);
      |  ^~~
met.cpp:12:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define cin(x)    scanf("%d",&x)
      |                   ~~~~~^~~~~~~~~
met.cpp:60:2: note: in expansion of macro 'cin'
   60 |  cin(m);
      |  ^~~
met.cpp:12:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define cin(x)    scanf("%d",&x)
      |                   ~~~~~^~~~~~~~~
met.cpp:64:3: note: in expansion of macro 'cin'
   64 |   cin(x);
      |   ^~~
met.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%lld",&reqd[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~
met.cpp:12:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define cin(x)    scanf("%d",&x)
      |                   ~~~~~^~~~~~~~~
met.cpp:69:2: note: in expansion of macro 'cin'
   69 |  cin(k);
      |  ^~~
met.cpp:12:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define cin(x)    scanf("%d",&x)
      |                   ~~~~~^~~~~~~~~
met.cpp:72:3: note: in expansion of macro 'cin'
   72 |   cin(ql[i]);
      |   ^~~
met.cpp:12:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define cin(x)    scanf("%d",&x)
      |                   ~~~~~^~~~~~~~~
met.cpp:73:3: note: in expansion of macro 'cin'
   73 |   cin(qr[i]);
      |   ^~~
met.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%lld",&qa[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21852 KB Output is correct
2 Correct 5 ms 21852 KB Output is correct
3 Correct 5 ms 21852 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 21852 KB Output is correct
2 Correct 5 ms 21848 KB Output is correct
3 Correct 5 ms 21848 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 24924 KB Output is correct
2 Correct 86 ms 28488 KB Output is correct
3 Correct 74 ms 26452 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 25808 KB Output is correct
2 Correct 78 ms 25900 KB Output is correct
3 Correct 85 ms 28776 KB Output is correct
4 Correct 25 ms 25692 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 25172 KB Output is correct
2 Correct 77 ms 29360 KB Output is correct
3 Correct 39 ms 21852 KB Output is correct
4 Correct 76 ms 26720 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 24520 KB Output is correct
2 Correct 77 ms 25816 KB Output is correct
3 Correct 57 ms 24660 KB Output is correct
4 Correct 91 ms 29928 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 38640 KB Output is correct
2 Correct 607 ms 25524 KB Output is correct
3 Correct 192 ms 22040 KB Output is correct
4 Correct 1321 ms 63244 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 750 ms 37416 KB Output is correct
2 Correct 669 ms 25508 KB Output is correct
3 Correct 181 ms 21980 KB Output is correct
4 Correct 1582 ms 65536 KB Output is correct