oj.uz

Submission #1003442

# Submission time Handle Problem Language Result Execution time Memory
1003442 2024-06-20T10:42:18 Z pcc Team Contest (JOI22_team) C++17
0 / 100
 7 ms 15708 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define _all(T) T.begin(),T.end()
#define tiii tuple<int,int,int>
#define ai3 array<int,3>

const int mxn = 3e5+10;
const int inf = 1e9+10;

struct BIT{
	int bit[mxn];
	vector<int> v;
	BIT(){}
	void init(){
		fill(bit,bit+mxn,INT_MIN);
		v.clear();
	}
	void reset(){
		for(auto &i:v)bit[i] = INT_MIN;
		v.clear();
	}
	void modify(int p,int val){
		for(;p<mxn;p+=p&-p){
			bit[p] = max(bit[p],val);
			v.push_back(p);
		}
		return;
	}
	int getval(int p){
		int re = INT_MIN;
		for(;p>0;p-= p&-p)re = max(re,bit[p]);
		return re;
	}
};

int ans = INT_MIN;
vector<int> alla,allb,allc;
array<int,3> arr[mxn];
vector<int> v[mxn];
vector<pii> ch[mxn];
int N;
BIT bit;

namespace PREC{
	void GO(){
		bit.init();
		for(int nowa = 1;nowa<alla.size();nowa++){
			for(auto &i:v[nowa]){
				int val = bit.getval(arr[i][1]-1);
				if(val>arr[i][2])ch[nowa].push_back(pii(arr[i][1],val));
				bit.modify(arr[i][1],arr[i][2]);
			}
		}
		bit.init();
		for(int nowa = 1;nowa<alla.size();nowa++){
			for(auto &i:v[nowa]){
				int val = bit.getval(arr[i][2]-1);
				if(val>arr[i][1])ch[nowa].push_back(pii(val,arr[i][2]));
				bit.modify(arr[i][2],arr[i][1]);
			}
		}
		return;
	}
}

namespace CDQ{
	void dc(int l,int r){
		if(l == r)return;
		int mid = (l+r)>>1;
		dc(l,mid);
		dc(mid+1,r);
		bit.reset();
		vector<ai3> vl,vr;//{b,c,val}
		for(int i = l;i<=mid;i++){
			for(auto &j:ch[i]){
				vl.push_back(ai3({j.fs,j.sc,allb[j.fs]+allc[j.sc]}));
			}
		}
		for(int i = mid+1;i<=r;i++){
			for(auto &j:v[i]){
				vr.push_back(ai3({arr[j][1],arr[j][2],alla[arr[j][0]]}));
			}
		}
		sort(vl.begin(),vl.end());
		sort(vr.begin(),vr.end());
		/*
		cerr<<l<<' '<<mid<<' '<<r<<":"<<endl;
		for(auto &i:vl)cerr<<i[0]<<' '<<i[1]<<' '<<i[2]<<',';cerr<<endl;
		for(auto &i:vr)cerr<<i[0]<<' '<<i[1]<<' '<<i[2]<<',';cerr<<endl;

	   */
		while(!vr.empty()||!vl.empty()){
			bool isl = false;
			if(vl.empty())isl = false;
			else if(vr.empty())isl = true;
			else if(vl.back()[0]>vr.back()[0])isl = true;
			else isl = false;
			if(isl){
				auto now = vl.back();vl.pop_back();
				//cerr<<"MODIFY:"<<now[0]<<' '<<now[1]<<' '<<now[2]<<endl;
				bit.modify(mxn-now[1],now[2]);
			}
			else{
				auto now = vr.back();vr.pop_back();
				//cerr<<"GETANS:"<<now[0]<<' '<<now[1]<<' '<<now[2]<<endl;
				int tval = bit.getval(mxn-(now[1]+1))+now[2];
				ans = max(ans,tval);
			}
		}
		return;
	}

	void GO(){
		dc(1,alla.size()-1);
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	alla = allb = allc = {-1};
	for(int i = 1;i<=N;i++){
		cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
		alla.push_back(arr[i][0]);
		allb.push_back(arr[i][1]);
		allc.push_back(arr[i][2]);
	}
	sort(alla.begin(),alla.end());alla.resize(unique(alla.begin(),alla.end())-alla.begin());
	sort(allb.begin(),allb.end());allb.resize(unique(allb.begin(),allb.end())-allb.begin());
	sort(allc.begin(),allc.end());allc.resize(unique(allc.begin(),allc.end())-allc.begin());
	for(int i = 1;i<=N;i++){
		arr[i][0] = lower_bound(_all(alla),arr[i][0])-alla.begin();
		arr[i][1] = lower_bound(_all(allb),arr[i][1])-allb.begin();
		arr[i][2] = lower_bound(_all(allc),arr[i][2])-allc.begin();
		v[arr[i][0]].push_back(i);
	}

	PREC::GO();
	//cerr<<"HI"<<endl;
	CDQ::GO();
/*
	for(int i = 0;i<alla.size();i++)cerr<<alla[i]<<',';cerr<<endl;
	for(int i = 0;i<allb.size();i++)cerr<<allb[i]<<',';cerr<<endl;
	for(int i = 0;i<allc.size();i++)cerr<<allc[i]<<',';cerr<<endl;
	for(int i = 1;i<alla.size();i++){
		cerr<<i<<":"<<endl;
		for(auto &j:ch[i])cerr<<j.fs<<','<<j.sc<<endl;
	}

*/

	cout<<ans<<'\n';
	return 0;
}

Compilation message

team.cpp: In function 'void PREC::GO()':
team.cpp:54:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for(int nowa = 1;nowa<alla.size();nowa++){
      |                    ~~~~^~~~~~~~~~~~
team.cpp:62:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int nowa = 1;nowa<alla.size();nowa++){
      |                    ~~~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15704 KB Output is correct
2 Correct 6 ms 15708 KB Output is correct
3 Incorrect 5 ms 15708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15704 KB Output is correct
2 Correct 6 ms 15708 KB Output is correct
3 Incorrect 5 ms 15708 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15708 KB Output is correct
2 Correct 7 ms 15576 KB Output is correct
3 Incorrect 7 ms 15704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15708 KB Output is correct
2 Correct 7 ms 15576 KB Output is correct
3 Incorrect 7 ms 15704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15708 KB Output is correct
2 Correct 7 ms 15576 KB Output is correct
3 Incorrect 7 ms 15704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15708 KB Output is correct
2 Correct 7 ms 15576 KB Output is correct
3 Incorrect 7 ms 15704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 15704 KB Output is correct
2 Correct 6 ms 15708 KB Output is correct
3 Incorrect 5 ms 15708 KB Output isn't correct
4 Halted 0 ms 0 KB -