oj.uz

Submission #976476

# Submission time Handle Problem Language Result Execution time Memory
976476 2024-05-06T15:18:24 Z MuhammadSaram Meteors (POI11_met) C++17
74 / 100
 5275 ms 64992 KB 
/********************* بسم الله الرحمن الرحيم ***********************/
 /******************** ٱلْحَمْدُ لِلَّٰهِ رَبِّ ٱلْعَالَمِينَ *************************/
/******************* Prophet Muhammad صلى الله عليه وسلم ************/
   /*********************** وَقُل رَّبِّ زِدْنِي عِلْمًا **************************/

#ifdef ONLINE_JUDGE
	#pragma GCC optimize("Ofast")
	#pragma GCC optimize("O3,unroll-loops")
	#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#else

#endif

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

#define int long long
#define endl '\n'
#define in binary_search
#define ll long long
#define ld long double
#define Hey ios::sync_with_stdio(false);
#define Welcome cin.tie(NULL), cout.tie(NULL);
#define all(v) v.begin(),v.end()

const int M = 1<<21;

int n,m,seg[M],lazy[M];

void push(int v,int s,int e)
{
	int mid=(s+e)/2,lc=v*2,rc=lc+1;
	seg[lc]+=(mid-s)*lazy[v],seg[rc]+=(e-mid)*lazy[v];
	lazy[lc]+=lazy[v],lazy[rc]+=lazy[v];
	lazy[v]=0;
}

void modify(int l,int r,int x,int v=1,int s=0,int e=m)
{
	if (l>=e or r<=s)
		return;
	if (l<=s and e<=r)
	{
		seg[v]+=x*(e-s);
		lazy[v]+=x;
		return;
	}
	int mid=(s+e)/2,lc=v*2,rc=lc+1;
	push(v,s,e);
	modify(l,r,x,lc,s,mid);
	modify(l,r,x,rc,mid,e);
	seg[v]=seg[lc]+seg[rc];
}

int get(int l,int r,int v=1,int s=0,int e=m)
{
	if (l>=e or r<=s)
		return 0;
	if (l<=s and e<=r)
		return seg[v];
	push(v,s,e);
	int mid=(s+e)/2,lc=v*2,rc=lc+1;
	return get(l,r,lc,s,mid)+get(l,r,rc,mid,e);
}

void solve()
{
	cin>>n>>m;
	vector<int> sps[n];
	int exp[n];
	for (int i=0;i<m;i++)
	{
		int x;
		cin>>x;
		sps[x-1].push_back(i);
	}
	for (int i=0;i<n;i++)
		cin>>exp[i];
	int k,lg=22;
	cin>>k;
	vector<vector<int>> que;
	for (int i=0;i<k;i++)
	{
		int l,r,x;
		cin>>l>>r>>x;
		l--;
		que.push_back({l,r,x});
	}
	unordered_map<int,vector<int>> mid;
	int ps[n][2];
	for (int i=0;i<n;i++)
		ps[i][0]=-1,ps[i][1]=1+k;
	for (int i=0;i<n;i++)
		mid[(ps[i][0]+ps[i][1])/2].push_back(i);
	while (!mid.empty())
	{
		unordered_map<int,vector<int>> mid1;
		for (int i=0;i<=k;i++)
		{
			if (mid.find(i)!=mid.end())
				for (int j:mid[i])
				{
					int su=0;
					for (int a:sps[j])
						su+=get(a,a+1);
					if (su>=exp[j])
						ps[j][1]=i;
					else
						ps[j][0]=i;
					if (ps[j][1]-ps[j][0]>1)
						mid1[(ps[j][0]+ps[j][1])/2].push_back(j);
				}
			if (i<k and que[i][0]<que[i][1])
				modify(que[i][0],que[i][1],que[i][2]);
			else if(i<k)
			{
				modify(que[i][0],m,que[i][2]);
				modify(0,que[i][1],que[i][2]);
			}
		}
		for (int i=0;i<M;i++)
			seg[i]=lazy[i]=0;
		mid=mid1;
	}
	for (int i=0;i<n;i++)
	{
		if (ps[i][1]==k+1)
			cout<<"NIE"<<endl;
		else
			cout<<ps[i][1]<<endl;
	}
}

signed main()
{
	Hey! Welcome // S'up
	
	int t = 1;
	// cin >> t;
	cout<<fixed<<setprecision(20);
	while (t--)
		solve();
	
	return 0;
}

Compilation message

met.cpp: In function 'void solve()':
met.cpp:80:8: warning: unused variable 'lg' [-Wunused-variable]
   80 |  int k,lg=22;
      |        ^~
met.cpp: In function 'int main()':
met.cpp:137:5: warning: value computed is not used [-Wunused-value]
  137 |  Hey! Welcome // S'up
      |     ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 33368 KB Output is correct
2 Correct 33 ms 33368 KB Output is correct
3 Correct 35 ms 33372 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 33372 KB Output is correct
2 Correct 31 ms 33368 KB Output is correct
3 Correct 37 ms 33420 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 37048 KB Output is correct
2 Correct 614 ms 38952 KB Output is correct
3 Correct 581 ms 38956 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 38180 KB Output is correct
2 Correct 566 ms 38224 KB Output is correct
3 Correct 578 ms 38856 KB Output is correct
4 Correct 149 ms 35472 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 37632 KB Output is correct
2 Correct 473 ms 39548 KB Output is correct
3 Correct 224 ms 36064 KB Output is correct
4 Correct 560 ms 39296 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 36540 KB Output is correct
2 Correct 534 ms 38276 KB Output is correct
3 Correct 528 ms 37020 KB Output is correct
4 Correct 573 ms 40512 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5275 ms 64992 KB Output is correct
2 Incorrect 3271 ms 51924 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5125 ms 62576 KB Output is correct
2 Incorrect 1983 ms 52404 KB Output isn't correct
3 Halted 0 ms 0 KB -