oj.uz

Submission #773175

# Submission time Handle Problem Language Result Execution time Memory
773175 2023-07-04T16:05:51 Z bgnbvnbv Pyramid Base (IOI08_pyramid_base) C++14
70 / 100
 1756 ms 262144 KB 
#include<iostream>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e6+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll st[4*maxN],lazy[4*maxN];
void down(ll id)
{
    ll &x=lazy[id];
    st[id*2]+=x;
    st[id*2+1]+=x;
    lazy[id*2+1]+=x;
    lazy[id*2]+=x;
    x=0;
}
#include<vector>
void update(ll i,ll j,ll v,ll id,ll l,ll r)
{
    if(j<l||r<i) return;
    if(i<=l&&r<=j)
    {
        //cout << id<<' '<<v<<'\n';
        st[id]+=v;
        lazy[id]+=v;
        return;
    }
    ll mid=l+r>>1;
    down(id);
    update(i,j,v,id*2,l,mid);
    update(i,j,v,id*2+1,mid+1,r);
    st[id]=min(st[id*2],st[id*2+1]);
}
ll n,m;
vector<int>in[maxN],out[maxN];
int p,x1[maxN],x2[maxN],y1[maxN],y2[maxN],c[maxN],b;
int cnt[maxN];
bool check(ll mid)
{
    for(int i=1;i<=m+1;i++) in[i].clear(),out[i].clear();
    for(int i=1;i<=p;i++)
    {
        cnt[max(x1[i]-mid+1,mid)]++;
        //cnt[min(x2[i]+mid,m-mid+1)]++;
        //cout <<max(x1[i]-mid+1,mid)<<' '<<min(x2[i]+mid,m-mid+1)<<'\n';
    }
    for(int i=mid;i<=m-mid+1;i++)
    {
        in[i].resize(cnt[i]);
    }
    for(int i=1;i<=p;i++)
    {
        in[max(x1[i]-mid+1,mid)][--cnt[max(x1[i]-mid+1,mid)]]=i;
    }
    for(int i=1;i<=p;i++)
    {
        cnt[min(x2[i]+mid,m-mid+1)]++;
    }
    for(int i=mid;i<=m-mid+1;i++)
    {
        out[i].resize(cnt[i]);
    }
    for(int i=1;i<=p;i++)
    {
         out[min(x2[i]+mid,m-mid+1)][--cnt[min(x2[i]+mid,m-mid+1)]]=i;
    }
    fill(st,st+4*maxN,0);
    fill(lazy,lazy+4*maxN,0);
    for(int i=mid;i<=m-mid;i++)
    {
        for(auto id:in[i])
        {
            ll l,r;
            l=max(y1[id]-mid+1,mid);
            r=min(y2[id]+mid-1,n-mid);
            update(l,r,c[id],1,mid,n-mid);
        }
        for(auto id:out[i])
        {
            ll l,r;
            l=max(y1[id]-mid+1,mid);
            r=min(y2[id]+mid-1,n-mid);
            update(l,r,-c[id],1,mid,n-mid);
        }

        if(st[1]<=b) return true;
    }
    return false;
}
void solve()
{
    cin >> m >> n;
    m*=2;
    n*=2;
    cin >> b;
    cin >> p;
    for(int i=1;i<=p;i++)
    {
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i] >> c[i];
        x1[i]--;
        //x2[i]--;
        y1[i]--;
        //y2[i]--;
        x1[i]*=2;
        y1[i]*=2;
        x2[i]*=2;
        y2[i]*=2;
    }
    ll low=1,high=min(m/2,n/2);
    while(low<=high)
    {
        ll mid=low+high>>1;
        if(check(mid)) low=mid+1;
        else high=mid-1;
    }
    cout << high;
    //cout << check(4);
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message

pyramid_base.cpp: In function 'void update(ll, ll, ll, ll, ll, ll)':
pyramid_base.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     ll mid=l+r>>1;
      |            ~^~
pyramid_base.cpp: In function 'void solve()':
pyramid_base.cpp:118:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  118 |         ll mid=low+high>>1;
      |                ~~~^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 219532 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 219496 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 219540 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 220036 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 221044 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 222752 KB Output is correct
2 Correct 677 ms 228372 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 685 ms 227868 KB Output is correct
2 Correct 464 ms 223164 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 220288 KB Output is correct
2 Correct 247 ms 220760 KB Output is correct
3 Correct 220 ms 220796 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 227020 KB Output is correct
2 Correct 518 ms 228304 KB Output is correct
3 Correct 450 ms 227836 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 636 ms 234688 KB Output is correct
2 Correct 263 ms 235892 KB Output is correct
3 Correct 254 ms 220940 KB Output is correct
4 Correct 971 ms 245308 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 895 ms 242536 KB Output is correct
2 Correct 1461 ms 248072 KB Output is correct
3 Correct 522 ms 230412 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 237376 KB Output is correct
2 Correct 1756 ms 255184 KB Output is correct
3 Correct 1649 ms 254548 KB Output is correct
4 Correct 1719 ms 254640 KB Output is correct
5 Correct 1712 ms 255280 KB Output is correct
6 Correct 435 ms 229420 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1437 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1525 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1220 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -