Submission #1126749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126749		modwwe	도로 건설 사업 (JOI13_construction)	C++20	0 / 100	7 ms	832 KiB

construction

#include<bits/stdc++.h>
//#define int   long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1<<k)
#define mp make_pair
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while (c < '0' || c > '9')
    {
        c = getchar_unlocked();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + c - '0';
        c = getchar_unlocked();
    }
    return x;
}
void phongbeo();
const int inf = 1e9;
const ll mod2 = 1e9+7;
const int  mod1 = 998244353;
const ll base=67;
int add(int x,int y)
{
    if(x+y>=mod2) x-=mod2;
    if(x+y<0)x+=mod2;
    return x+y;
}
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a, b, c;
};
struct id
{
    int a, b, c, d;
};
struct ie
{
    int a, b, c, d, e;

};
int n, m,s1,s2,s4, s3, sf, k, s5, s6, mx, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2, r2, center;
int  i, s10, s12,k1,k2,k3,s11,lim,w,l,r ;
int kk;
int el = 19;
main()
{
    if(fopen(task".inp","r"))
    {
        fin(task);
        fou(task);
    }
    NHP
    /// cin>>s1;
    // modwwe
    phongbeo();
    // checktime
}
ib ans;
ib mer(ib a,int b)
{
    if(b>a.a)return {b,1};
    if(a.a==b)return {a.a,a.b+1};
    return a;
}
int a[400001];
int b[400001];
int posa[400001];
int posb[400001];
vector<ib> v,v2;
struct st
{
    int tmin[1200001];
    int tmax[1200001];
    vector<ib> vc;
    void res(vector<ib>&v)
    {
        vc=v;
    }
    void init(int node,int l,int r,int l1)
    {
        if(l==r)
        {
            tmin[node]=tmax[node]=0;
            /// if(vc[l-1].b==1) cout<<node,down
            return;
        }
        int mid=l+r>>1;
        if(l1<=mid)
            init(node<<1,l,mid,l1);
        else init(node<<1|1,mid+1,r,l1);
        tmin[node]=min(tmin[node<<1],tmin[node<<1|1]);
        tmax[node]=max(tmax[node<<1],tmax[node<<1|1]);
    }
    void upd(int node,int l,int r,int x,int y,int k)
    {

        if(vc[l-1].a==y&&vc[r-1].a==y) return;
        if(tmin[node]==-1&&tmax[node]==-1) return;
        if(tmin[node]==x&&tmax[node]==x) return;
        if(l==r)
        {
            assert(tmin[node]!=-1);
            if(tmin[node]==0) tmin[node]=tmax[node]=x;
            else
            {
                tmin[node]=tmax[node]=-1;
                ans=mer(ans,k-vc[l-1].b);
            }
            return;
        }
        int mid=l+r>>1;
        upd(node<<1,l,mid,x,y,k);
        upd(node<<1|1,mid+1,r,x,y,k);
        tmin[node]=min(tmin[node<<1],tmin[node<<1|1]);
        tmax[node]=max(tmax[node<<1],tmax[node<<1|1]);
    }
    void hihi(int node,int l,int r)
    {
        if(tmin[node]==-1&&tmax[node]==-1) return;
        if(l==r)
        {
            ans=mer(ans,n+1-vc[l-1].b);
            return;
        }
        int mid=l+r>>1;
        hihi(node<<1,l,mid);
        hihi(node<<1|1,mid+1,r);
    }
} st[2];
bool cmp(ib a,ib b)
{
    return a.a<b.a;
}
void phongbeo()
{
    cin>>n;
    int bmin=inf;
    int bmax=0;
    int amin=inf;
    int amax=inf;
    for(int i=1; i<=n; i++)
    {
        cin>>l>>r>>s2;
        a[i]=l-r;
        b[i]=l+s2;
        v2.pb({b[i],i});
        v.pb({a[i],i});
        bmin=min(bmin,b[i]);
        bmax=max(bmax,b[i]);
        amin=min(amin,a[i]);
        amax=max(amax,a[i]);
    }
    if(amin==amax||bmin==bmax)
    {
        cout<<-1;
         exit(0);
    }
    sort(v.begin(),v.end(),cmp);
    sort(v2.begin(),v2.end(),cmp);
    for(int i=0; i<n; i++)
        posa[v[i].b]=i+1,
                     posb[v2[i].b]=i+1;
    st[0].res(v);
    st[1].res(v2);
    for(int i=1; i<=4*n; i++)
        for(int f=0; f<2; f++)
            st[f].tmin[i]=-1,st[f].tmax[i]=-1;
    for(int i=1; i<=n; i++)
    {
        st[0].init(1,1,n,posa[i]);
        st[1].init(1,1,n,posb[i]);
        st[0].upd(1,1,n,b[i],a[i],i);
        st[1].upd(1,1,n,a[i],b[i],i);
    }
    st[0].hihi(1,1,n);
    st[1].hihi(1,1,n);
    cout<<ans.a<<" "<<ans.b;
}

Compilation message (stderr)

construction.cpp:73:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   73 | main()
      | ^~~~
construction.cpp: In function 'int main()':
construction.cpp:11:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
construction.cpp:77:9: note: in expansion of macro 'fin'
   77 |         fin(task);
      |         ^~~
construction.cpp:12:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
construction.cpp:78:9: note: in expansion of macro 'fou'
   78 |         fou(task);
      |         ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30