Submission #361324

#	Time	Username	Problem	Language	Result	Execution time	Memory
361324		Dymo	도로 건설 사업 (JOI13_construction)	C++14	0 / 100	37 ms	3344 KiB

construction

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn =1e6+10;
const ll mod=1e9+7;
const ll base=1e8;

ll a[maxn][2];

map<ll,vector<pll>> mp[2];
ll len[2];
ll st[4*maxn][2];
ll la[4*maxn][2];
void dosth(ll id,ll left,ll right,ll t)
{
   if (left==right||la[id][t]==0) return ;
   ll mid=(left+right)/2;
   st[id*2][t]+=la[id][t]*(mid-left+1);
   la[id*2][t]+=la[id][t];
   st[id*2+1][t]+=la[id][t]*(right-mid);
   la[id*2+1][t]+=la[id][t];
   la[id][t]=0;

}
void update(ll id,ll left,ll right,ll x,ll y,ll diff,ll t)
{
    dosth(id,left,right,t);
   if (x>right||y<left) return ;
   if (x<=left&&y>=right)
   {
       st[id][t]+=diff*(right-left+1);
       la[id][t]+=diff;
       dosth(id,left,right,t);
       return ;
   }
   ll mid=(left+right)/2;
   update(id*2,left,mid,x,y,diff, t);
   update(id*2+1, mid+1, right, x, y, diff,t);
   st[id][t]=st[id*2][t]+st[id*2+1][t];
}
ll get(ll id,ll left,ll right,ll x,ll y,ll t)
{
    dosth(id,left,right,t);
    if (x>right||y<left) return 0;
    if (x<=left&&y>=right)return st[id][t];
    ll mid=(left+right)/2;
    return get(id*2,left,mid,x,y,t)+get(id*2+1, mid+1, right, x, y, t);
}
ll par[maxn];
ll find_par(ll u)
{
    if (u==par[u]) return u;
    return par[u]=find_par(par[u]);
}
bool dsu(ll x,ll y)
{
    x=find_par(x);
    y=find_par(y);
    if (x==y) return false;
    par[x]=y;
    return true;

}
ll f[maxn];
ll b[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
    ll n, m, c;
     cin>> n>> m>> c;
     vector<ll> vt[3];
     for (int i=1;i<=n;i++)
     {
         cin>>a[i][0]>>a[i][1];
          for (int j=0;j<=1;j++)
          {
              mp[j][a[i][j]].pb(make_pair(a[i][1-j],i));
              vt[j].pb(a[i][1-j]);
          }
     }

     vector<pair<pll,pll>> even[2];
     for (int i=1;i<=m;i++)
     {
         ll x, y, x1, y1;
          cin>> x>> y>>x1 >> y1;
          even[0].pb(make_pair(make_pair(x,1),make_pair(y,y1)));
          even[0].pb(make_pair(make_pair(x1+1,-1),make_pair(y,y1)));
          even[1].pb(make_pair(make_pair(y,1),make_pair(x,x1)));
          even[1].pb(make_pair(make_pair(y1+1,-1),make_pair(x,x1)));
          vt[0].pb(y);
          vt[0].pb(y1);
          vt[1].pb(x);
          vt[1].pb(x1);
     }
     for (int t=0;t<=1;t++)
     {
         sort(vt[t].begin(),vt[t].end());
         vt[t].resize(unique(vt[t].begin(),vt[t].end())-vt[t].begin());
     }
    for (int i=0;i<=1;i++)  sort(even[i].begin(),even[i].end());
     for (int j=0;j<=1;j++)
     {
         len[j]=vt[j].size();
     }
     vector<pair<ll,pll>> ed;
     for (int i=0;i<=1;i++)
     {
         ll idnw=0;
         for (auto p:mp[i])
         {
             ll pos=p.ff;
             while (idnw<even[i].size()&&even[i][idnw].ff.ff<=pos)
             {
                 ll x=even[i][idnw].ss.ff;
                 ll y=even[i][idnw].ss.ss;
                 x=lower_bound(vt[i].begin(),vt[i].end(),x)-vt[i].begin()+1;
                 y=lower_bound(vt[i].begin(),vt[i].end(),y)-vt[i].begin()+1;
                  ll diff=even[i][idnw].ff.ss;
                /* if (i==1)
                 {
                     cout <<x<<" "<<y<<" "<<idnw<<" "<<even[i][idnw].ss.ff<<" "<<even[i][idnw].ss.ss<<" "<<diff<<endl;
                     for (auto to:vt[i])
                     {
                         cout <<to<<" ";
                     }
                     cout <<endl;
                 }*/

                 update(1,1,len[i],x,y,diff,i);
                 idnw++;
             }
             auto vt1=p.ss;
             sort(vt1.begin(),vt1.end());
             ll t=i;
            // if (i==1) cout <<vt1.size()<<endl;
             for (int i=1;i<vt1.size();i++)
             {
                ll x=vt1[i-1].ff;
                ll y=vt1[i].ff;
                x=lower_bound(vt[t].begin(),vt[t].end(),x)-vt[t].begin()+1;
                y=lower_bound(vt[t].begin(),vt[t].end(),y)-vt[t].begin()+1;
                ll h=get(1,1,len[t],x,y,t);
                if (!h)
                {
                ll id1=vt1[i-1].ss;
                ll id2=vt1[i].ss;
                /*if (t==0)
                {
                    cout <<id1<<" "<<id2<<" "<<x<<" "<<y<<endl;
                }*/
                ed.pb(make_pair(vt1[i].ff-vt1[i-1].ff,make_pair(id1,id2)));
                }
             }
         }
     }
     for (int i=1;i<=n;i++)
     {
         par[i]=i;
     }
     ll cnt=0;
     /*cout <<ed.size()<<endl;
     for (auto to:ed)
     {
         cout <<to.ff<<" "<<to.ss.ff<<" "<<to.ss.ss<<endl;
     }*/
     for (auto to:ed)
     {
         ll w=to.ff;
         //cout <<to.ss.ff<<" "<<to.ss.ss<<" "<<find_par(to.ss.ff)<<" "<<find_par(to.ss.ss)<<endl;
        if(dsu(to.ss.ff,to.ss.ss))
         {
             cnt++;
             b[cnt]=w;
             f[cnt]=f[cnt-1]+w;
         }
     }
     for (int i=1;i<=c;i++)
     {
         ll x, y;
          cin>> x>> y;
          if (cnt+y<n)
          {
              cout <<-1<<endl;
          }
          else
          {
              ll l=1, h=cnt;
            //  cout <<l<<" "<<h<<endl;
              while (l<=h)
              {
                  ll mid=(l+h)/2;
                 //  cout <<mid<<" "<<b[mid]<<" "<<x<<endl;
                  if (b[mid]>x) h=mid-1;
                  else l=mid+1;
              }
             l=max(l,n-y+1);
              ll ans=f[l-1]+(n-l+1)*x;
              cout <<ans<<endl;
          }
     }




}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:127:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |              while (idnw<even[i].size()&&even[i][idnw].ff.ff<=pos)
      |                     ~~~~^~~~~~~~~~~~~~~
construction.cpp:151:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  151 |              for (int i=1;i<vt1.size();i++)
      |                           ~^~~~~~~~~~~
construction.cpp:80:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   80 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
construction.cpp:81:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   81 |         freopen("test.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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