Submission #1128528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128528		rasbery303	Meteors (POI11_met)	C++20	100 / 100	1266 ms	58992 KiB

met

#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 (stderr)

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:9: 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:9: 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:17: note: in expansion of macro 'cin'
   64 |                 cin(x);
      |                 ^~~
met.cpp:68:22: 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:9: 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:17: 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:17: note: in expansion of macro 'cin'
   73 |                 cin(qr[i]);
      |                 ^~~
met.cpp:74:22: 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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13