| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 719797 |
2023-04-06T17:20:01 Z |
lam |
Team Contest (JOI22_team) |
C++14 |
|
1 ms |
468 KB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e3 + 10;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
#define ff first
#define ss second
int n,m,k;
iii a[maxn];
vector <iii> d;
ii vval;
int f[maxn],f2[maxn];
vector <int> comps_y,comps_z;
int update(int x, int val)
{
assert(x!=0);
while (x<=m)
{
f[x]=max(f[x],val);
x+=(x&-x);
}
}
int get(int x)
{
assert(x>=0&&x<=m);
int temp=-1e9;
while (x>0)
{
temp=max(temp,f[x]);
x-=(x&-x);
}
return temp;
}
void update2(int x, int val)
{
assert(x>=0&&x<=k);
while (x<=k)
{
f2[x]=max(f2[x],val);
x+=(x&-x);
}
}
int get2(int x)
{
int temp=-1e9;
assert(x>=0&&x<=k);
while (x>0)
{
temp=max(temp,f2[x]);
x-=(x&-x);
}
return temp;
}
inline int get_idy(iii x)
{
return lower_bound(comps_y.begin(),comps_y.end(),x.ss.ff) - comps_y.begin()+1;
}
inline int get_idz(iii x)
{
return lower_bound(comps_z.begin(),comps_z.end(),x.ss.ss) - comps_z.begin()+1;
}
void add(iii x)
{
int y = lower_bound(comps_y.begin(),comps_y.end(),x.ss.ff) - comps_y.begin()+1;
int z = lower_bound(comps_z.begin(),comps_z.end(),x.ss.ss) - comps_z.begin()+1;
int mmax = get(y-1);
if (mmax > z) vval = max(vval,make_pair(y,mmax));
update2(z,y);
}
void add2(iii x)
{
int y = lower_bound(comps_y.begin(),comps_y.end(),x.ss.ff) - comps_y.begin()+1;
int z = lower_bound(comps_z.begin(),comps_z.end(),x.ss.ss) - comps_z.begin()+1;
assert(y!=0);
update(y,z);
int idx = get2(z-1);
// if (idx!=-1e9) vval=max(vval,make_pair(idx,z));
}
int query(iii x)
{
int y=x.ss.ff;
int ans=-1;
if (vval.ff!=-1) assert(vval.ff>0&&vval.ss>0);
if (vval.ff!=-1&&comps_z[vval.ss-1]>x.ss.ss&&comps_y[vval.ff-1]>y) ans=max(ans,comps_y[vval.ff-1]+comps_z[vval.ss-1]+x.ff);
return ans;
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin>>n;
for (int i=1; i<=n; i++) cin>>a[i].ff>>a[i].ss.ff>>a[i].ss.ss;
for (int i=1; i<=n; i++)
{
comps_y.push_back(a[i].ss.ff);
comps_z.push_back(a[i].ss.ss);
}
sort(comps_y.begin(),comps_y.end());
comps_y.resize(unique(comps_y.begin(),comps_y.end())-comps_y.begin());
sort(comps_y.begin(),comps_y.end());
sort(comps_z.begin(),comps_z.end());
comps_z.resize(unique(comps_z.begin(),comps_z.end())-comps_z.begin());
sort(comps_z.begin(),comps_z.end());
m=comps_y.size();
k=comps_z.size();
fill_n(f,m+1,-1e9);
fill_n(f2,k+1,-1e9);
sort(a+1,a+n+1);
d.clear();
int l,r;
int ans=-1;
vval={-1,-1};
for (int i=1; i<=n; i++)
{
if (i==1||a[i].ff!=a[i-1].ff) l=i;
if (i==n||a[i].ff!=a[i+1].ff)
{
r=i;
int l2,r2;
// for (int j=l; j<=r; j++)
// {
// if (j==l||a[j].ss.ff!=a[j-1].ss.ff) l2=j;
// if (j==r||a[j].ss.ff!=a[j+1].ss.ff)
// {
// r2=j;
// ans=max(ans,query(a[l2]));
// ans=max(ans,query(a[r2]));
// }
// }
// for (int j=l; j<=r; j++)
// {
// if (j==l||a[j].ss.ff!=a[j-1].ss.ff) l2=j;
// if (j==r||a[j].ss.ff!=a[j+1].ss.ff)
// {
// r2=j;
// add(a[r2]);
// add(a[l2]);
// }
// }
for (int j=l; j<=r; j++)
{
if (j==l||a[j].ss.ff!=a[j-1].ss.ff) l2=j;
if (j==r||a[j].ss.ff!=a[j+1].ss.ff)
{
r2=j;
assert(l2>0&&l2<=r2&&r2>0&&r2<=r);
add2(a[l2]);
add2(a[r2]);
assert(false);
}
}
}
}
cout<<ans<<'\n';
}
Compilation message
team.cpp: In function 'void add2(iii)':
team.cpp:87:9: warning: unused variable 'idx' [-Wunused-variable]
87 | int idx = get2(z-1);
| ^~~
team.cpp: In function 'long long int update(long long int, long long int)':
team.cpp:24:1: warning: control reaches end of non-void function [-Wreturn-type]
24 | }
| ^
team.cpp: In function 'int main()':
team.cpp:159:25: warning: 'l2' may be used uninitialized in this function [-Wmaybe-uninitialized]
159 | add2(a[l2]);
| ~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
