oj.uz

Submission #740010

# Submission time Handle Problem Language Result Execution time Memory
740010 2023-05-11T23:16:41 Z tolbi Catfish Farm (IOI22_fish) C++17
0 / 100
 1000 ms 44284 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
#define author tolbi
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
template<typename X, typename Y> istream& operator>>(istream& in, pair<X,Y> &pr) {return in>>pr.first>>pr.second;}
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X, typename Y> pair<X,Y> operator+(pair<X,Y> a, pair<X,Y> b) {pair<X,Y> c; c.first=a.first+b.first,c.second=a.second+b.second;return c;}
template<typename X, typename Y> pair<X,Y> operator-(pair<X,Y> a, pair<X,Y> b) {pair<X,Y> c; c.first=a.first-b.first,c.second=a.second-b.second;return c;}
template<typename X, typename Y> void operator+=(pair<X,Y> &a, pair<X,Y> b){a.first+=b.first,a.second+=b.second;}
template<typename X, typename Y> void operator-=(pair<X,Y> &a, pair<X,Y> b){a.first-=b.first,a.second-=b.second;}
template<typename X> istream& operator>>(istream& in, vector<X> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X> ostream& operator<<(ostream& os, vector<X> arr) {for(auto &it : arr) os<<it<<" "; return os;}
template<typename X, size_t Y> istream& operator>>(istream& in, array<X,Y> &arr) {for(auto &it : arr) in>>it; return in;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> arr) {for(auto &it : arr) os<<it<<" "; return os;}
#define int long long
#define endl '\n'
#define vint(x) vector<int> x
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for (auto &it : x) cin>>it;
#define coutarr(x) for (auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(),x.end())
#define sortrarr(x) sort(x.rbegin(),x.rend())
#define det(x) cout<<"NO\0YES"+x*3<<endl;
#define INF LONG_LONG_MAX
#define rev(x) reverse(x.begin(),x.end());
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define tol(bi) (1LL<<((int)(bi)))
const int MOD = 1e9+7;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());


struct SegTree{
	vector<int> segtree;
	vector<bool> lazy;
	SegTree(int n){
		segtree.resize(tol(ceil(log2(n)+1))-1,0ll);
		lazy.resize(segtree.size(), false);
	}
	void dallan(int node){
		if (!lazy[node]) return;
		segtree[node]=0ll;
		if (node*2+1<segtree.size()){
			lazy[node*2+1]=lazy[node*2+2]=true;
		}
		lazy[node]=false;
	}
	void update(int pos, int val, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		dallan(node);
		if (l==pos && r==pos) {
			segtree[node]=max(segtree[node],val);
			return;
		}
		if (l>pos || r<pos) return;
		int mid = l+(r-l)/2;
		update(pos, val, l, mid, node*2+1);
		update(pos, val, mid+1, r, node*2+2);
		segtree[node]=max(segtree[node*2+1],segtree[node*2+2]);
	}
	int query(int tarl, int tarr, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = segtree.size()/2;
		dallan(node);
		if (l>=tarl && r<=tarr) return segtree[node];
		if (l>tarr || r<tarl) return 0ll;
		int mid = l+(r-l)/2;
		int lnode = query(tarl, tarr, l, mid, node*2+1);
		int rnode = query(tarl, tarr, mid+1, r, node*2+2);
		return max(lnode, rnode);
	}
	void reset(){
		lazy[0]=true;
		dallan(0);
	}
};
long long max_weights(int32_t n, int32_t m, vector<int32_t> x, vector<int32_t> y, vector<int32_t> w) {
	vector<SegTree> segtree(4,SegTree(n));
	vector<SegTree> old(4,SegTree(n));
	vector<pair<pair<int,int>,int>> arr(m);
	for (int i = 0; i < m; i++){
		arr[i]={{x[i],y[i]},w[i]};
	}
	sort(arr.begin(), arr.end(), [&](pair<pair<int,int>,int> a, pair<pair<int,int>,int> b){
		return a.first.second<b.first.second;
	});
	vector<vector<pair<int,int>>> pts(n+1);
	pts[n].push_back({-1,0});
	for (int i = 0; i < n; ++i)
	{
		pts[i].push_back({0,0});
	}
	for (int i = 0; i < m; ++i)
	{
		pts[arr[i].first.first].push_back({arr[i].first.second,arr[i].second});
	}
	for (int i = 0; i < n; i++){
		pts[i].push_back({n,0});
		for (int j = 1; j < pts[i].size(); j++){
			pts[i][j].second+=pts[i][j-1].second;
		}
	}
	auto lbin = [&](int xpos, int ypos)->int{
		int l = 0, r = pts[xpos].size()-1;
		while (l<r){
			int mid = l+(r-l+1)/2;
			if (pts[xpos][mid].first<=ypos){
				l=mid;
			}
			else {
				r=mid-1;
			}
		}
		return l;
	};
	int ans = 0;
	for (int i = n-1; i >= 0; i--){
		segtree[0].reset();
		segtree[1].reset();
		segtree[2].reset();
		segtree[3].reset();
		for (int j = 1; j < pts[i].size(); j++){
			int he = pts[i][j].first-1;
			int we = pts[i][j].second;
			int kk = 0;
			if (j) kk = pts[i][j-1].second;
			int art = old[0].query(he+1,n-1)-kk;
			int azl = max(old[1].query(0,he)+pts[i+1][lbin(i+1,he)].second,old[2].query(0,he));
			art=max(art,0ll);
			azl=max(azl,0ll);
			ans=max(ans,art);
			ans=max(ans,azl);
			if (i==3 && he==2){
				//cout<<he<<endl;
				//cout<<lbin(i+1,he)<<endl;
			}
			//cout<<i<<" "<<he<<" "<<art<<" "<<azl<<endl;
			if (i==0) break;
			segtree[0].update(he,pts[i-1][lbin(i-1,he)].second+max(art,azl));
			segtree[3].update(he,max(art,azl));
			segtree[1].update(he,azl-kk);
			segtree[2].update(he+1,old[3].query(0,he));
			segtree[2].update(he+1,old[0].query(he+1,n-1)-we);
		}
		swap(old,segtree);
	}
	return ans;
}




#ifdef tolbi
int32_t main(){
	ios;
	int t=1;
	int tno = 0;
	if (!t) cin>>t;
	while (t-(tno++)){
		int32_t n,m;cin>>n>>m;
		vector<int32_t> x(m),y(m),z(m);
		for (int i = 0; i < m; i++){
			cin>>x[i]>>y[i]>>z[i];
		}
		cout<<max_weights(n,m,x,y,z)<<endl;
	}
}
#endif

Compilation message

fish.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      | 
fish.cpp: In member function 'void SegTree::dallan(long long int)':
fish.cpp:53:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   if (node*2+1<segtree.size()){
      |       ~~~~~~~~^~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:108:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   for (int j = 1; j < pts[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~
fish.cpp:131:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   for (int j = 1; j < pts[i].size(); j++){
      |                   ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 29284 KB Output is correct
2 Correct 255 ms 30924 KB Output is correct
3 Correct 212 ms 24104 KB Output is correct
4 Correct 211 ms 24028 KB Output is correct
5 Execution timed out 1008 ms 44284 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 443 ms 34372 KB Output is correct
3 Correct 533 ms 42436 KB Output is correct
4 Correct 230 ms 30536 KB Output is correct
5 Correct 253 ms 32776 KB Output is correct
6 Incorrect 0 ms 300 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 24048 KB Output is correct
2 Correct 221 ms 24144 KB Output is correct
3 Incorrect 274 ms 27876 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '1999989354'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '4044', found: '2022'
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 24048 KB Output is correct
2 Correct 221 ms 24144 KB Output is correct
3 Incorrect 274 ms 27876 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '1999989354'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 29284 KB Output is correct
2 Correct 255 ms 30924 KB Output is correct
3 Correct 212 ms 24104 KB Output is correct
4 Correct 211 ms 24028 KB Output is correct
5 Execution timed out 1008 ms 44284 KB Time limit exceeded
6 Halted 0 ms 0 KB -