oj.uz

Submission #361328

# Submission time Handle Problem Language Result Execution time Memory
361328 2021-01-29T10:14:06 Z Dymo 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 3339 ms 150596 KB 
#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("t.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;
     sort(ed.begin(),ed.end());
     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;
          //   cout <<to.ss.ff<<" "<<to.ss.ss<<endl;
         }
     }
     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

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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3472 KB Output is correct
2 Correct 770 ms 45256 KB Output is correct
3 Correct 736 ms 44360 KB Output is correct
4 Correct 461 ms 33196 KB Output is correct
5 Correct 733 ms 43860 KB Output is correct
6 Correct 738 ms 44704 KB Output is correct
7 Correct 229 ms 29780 KB Output is correct
8 Correct 451 ms 49992 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3472 KB Output is correct
2 Correct 770 ms 45256 KB Output is correct
3 Correct 736 ms 44360 KB Output is correct
4 Correct 461 ms 33196 KB Output is correct
5 Correct 733 ms 43860 KB Output is correct
6 Correct 738 ms 44704 KB Output is correct
7 Correct 229 ms 29780 KB Output is correct
8 Correct 451 ms 49992 KB Output is correct
9 Correct 3168 ms 98856 KB Output is correct
10 Correct 3138 ms 98788 KB Output is correct
11 Correct 3167 ms 98884 KB Output is correct
12 Correct 3281 ms 98660 KB Output is correct
13 Correct 1157 ms 53604 KB Output is correct
14 Correct 721 ms 43836 KB Output is correct
15 Correct 3141 ms 98596 KB Output is correct
16 Correct 773 ms 72040 KB Output is correct
17 Correct 779 ms 71912 KB Output is correct
18 Correct 890 ms 140044 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3472 KB Output is correct
2 Correct 770 ms 45256 KB Output is correct
3 Correct 736 ms 44360 KB Output is correct
4 Correct 461 ms 33196 KB Output is correct
5 Correct 733 ms 43860 KB Output is correct
6 Correct 738 ms 44704 KB Output is correct
7 Correct 229 ms 29780 KB Output is correct
8 Correct 451 ms 49992 KB Output is correct
9 Correct 959 ms 51784 KB Output is correct
10 Correct 968 ms 50852 KB Output is correct
11 Correct 965 ms 49736 KB Output is correct
12 Correct 622 ms 37804 KB Output is correct
13 Correct 899 ms 54604 KB Output is correct
14 Correct 1012 ms 53576 KB Output is correct
15 Correct 975 ms 51912 KB Output is correct
16 Correct 969 ms 51548 KB Output is correct
17 Correct 386 ms 34740 KB Output is correct
18 Correct 699 ms 51912 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3472 KB Output is correct
2 Correct 770 ms 45256 KB Output is correct
3 Correct 736 ms 44360 KB Output is correct
4 Correct 461 ms 33196 KB Output is correct
5 Correct 733 ms 43860 KB Output is correct
6 Correct 738 ms 44704 KB Output is correct
7 Correct 229 ms 29780 KB Output is correct
8 Correct 451 ms 49992 KB Output is correct
9 Correct 3168 ms 98856 KB Output is correct
10 Correct 3138 ms 98788 KB Output is correct
11 Correct 3167 ms 98884 KB Output is correct
12 Correct 3281 ms 98660 KB Output is correct
13 Correct 1157 ms 53604 KB Output is correct
14 Correct 721 ms 43836 KB Output is correct
15 Correct 3141 ms 98596 KB Output is correct
16 Correct 773 ms 72040 KB Output is correct
17 Correct 779 ms 71912 KB Output is correct
18 Correct 890 ms 140044 KB Output is correct
19 Correct 959 ms 51784 KB Output is correct
20 Correct 968 ms 50852 KB Output is correct
21 Correct 965 ms 49736 KB Output is correct
22 Correct 622 ms 37804 KB Output is correct
23 Correct 899 ms 54604 KB Output is correct
24 Correct 1012 ms 53576 KB Output is correct
25 Correct 975 ms 51912 KB Output is correct
26 Correct 969 ms 51548 KB Output is correct
27 Correct 386 ms 34740 KB Output is correct
28 Correct 699 ms 51912 KB Output is correct
29 Correct 3315 ms 106392 KB Output is correct
30 Correct 1957 ms 87856 KB Output is correct
31 Correct 3292 ms 100324 KB Output is correct
32 Correct 953 ms 46540 KB Output is correct
33 Correct 3265 ms 100308 KB Output is correct
34 Correct 991 ms 48048 KB Output is correct
35 Correct 3238 ms 150596 KB Output is correct
36 Correct 3339 ms 105412 KB Output is correct
37 Correct 933 ms 77284 KB Output is correct
38 Correct 1053 ms 143544 KB Output is correct
39 Correct 723 ms 65480 KB Output is correct