Submission #885889

#	Time	Username	Problem	Language	Result	Execution time	Memory
885889		ByeWorld	Team Contest (JOI22_team)	C++14	100 / 100	190 ms	26848 KiB

team

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 3e5+20;
const int LOG = 60;
const int MOD = 998244353;
const int SQRT = 520;
const int INF = 1e18;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
 
int n;
vector <ipii> vec;
int oz = -INF, oy = -INF; 
set <pii> by, bz; // by --> {y, z}
int ans = -1;

signed main(){
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++){
        int x, y, z; cin >> x >> y >> z;
        vec.pb({{x, y}, z});
    }
    vec.pb({{-1, -1}, -1});
    sort(vec.begin(), vec.end());
    //for(auto in : vec) cout << in.fi.fi << ' ' << in.fi.se << ' ' << in.se << " in\n";
    
    for(int i=1,j=1; i<=n; i++){
        while(vec[j].fi.fi < vec[i].fi.fi){
            int x = vec[j].fi.fi; int y = vec[j].fi.se; int z = vec[j].se;
            j++;
            //insert
            if(y<=oy && z<=oz) continue; // gk di insert
            
            if(by.empty()){
                if (y >= oy && z >= oz) {
                    by.insert({y, z}); bz.insert({z, y});
                }
                else if (y > oy) {
                    oy = y;
                }
                else if (z > oz) {
                    oz = z;
                }
                continue;
            }
            
            auto it = by.lower_bound(pii(y, z));
            if(!by.empty() && (*it)==pii(y,z)) continue;
            
        
            if(it == by.begin()){
                if(z < it->se){
                    if (y >= oy && z >= oz) {
                        by.insert({y, z}); bz.insert({z, y});
                    }
                    else if (y > oy) {
                        oy = y;
                    }
                    else if (z > oz) {
                        oz = z;
                    }
                }
                else if(z > it->se){
                    auto nx = bz.lower_bound(pii(z, -1));
                    nx--; //pasti ada
                    oy = (*nx).se; oz = z;
                    
                    auto lst = nx;
                    lst++;
                    auto te = bz.begin();
                    while(true) {
                        by.erase(pii((*te).se, (*te).fi)); 
                        auto te2 = te; te++; 
                        bz.erase(te2); 
                        if(te==lst) break;
                    }
                }
                else{
                    if (y < oy) {
                        oz = z;
                    }
                    else {
                        by.insert({y, z}); bz.insert({z, y});
                    }
                }
                continue;
            }
            
            auto it2 = it; it2--;
            pii bef = (*it2);
            
            if(it == by.end()){
                if(z >= (*it2).se){
                    by.insert({y, z}); bz.insert({z, y});
                } else {
                    oy = y; oz = (*it2).se;
                    by.clear(); bz.clear();
                }
                continue;
            }
            
            if(bef.se > z){
                oy = y; oz = bef.se; 
            
                auto te = by.begin();
                while(true) {
                    bz.erase(pii((*te).se, (*te).fi)); 
                    auto te2 = te; te++; 
                    by.erase(te2); 
                    if(te==it) break;
                }
                
            } else if(bef.se <= z && z <= (*it).se){ //insert
                by.insert({y, z}); bz.insert({z, y});
            } else { // new pair
                auto nx = bz.lower_bound(pii(z, -1));
                nx--; //pasti ada
                oy = (*nx).se; oz = z;
                
                auto lst = nx;
                lst++;
                auto te = bz.begin();
                while(true) {
                    by.erase(pii((*te).se, (*te).fi)); 
                    auto te2 = te; te++; 
                    bz.erase(te2); 
                    if(te==lst) break;
                }
            }
        }
        
        
        int x = vec[i].fi.fi; int y = vec[i].fi.se; int z = vec[i].se;
        
        //for(auto in : by) cout << in.fi << ' ' << in.se << " in\n"; 
        //cout << i << " ii\n";
        if(y<oy && z<oz) ans = max(ans, x+oy+oz);
        
    }
    cout << ans << '\n';
}

Compilation message (stderr)

team.cpp: In function 'int main()':
team.cpp:41:17: warning: unused variable 'x' [-Wunused-variable]
   41 |             int x = vec[j].fi.fi; int y = vec[j].fi.se; int z = vec[j].se;
      |                 ^

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 27 / 27