oj.uz

Submission #213333

# Submission time Handle Problem Language Result Execution time Memory
213333 2020-03-25T15:34:51 Z mhy908 Pyramid Base (IOI08_pyramid_base) C++14
70 / 100
 5000 ms 97628 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=1987654321987654321;
const int inf=2000000000;
int n, m, p;
pair<pair<pii, pii>, LL> rect[400010];
LL b, tree[4000010], lazy[4000010];
void init(int point, int s, int e){
    tree[point]=lazy[point]=0;
    if(s==e)return;
    init(point*2, s, (s+e)/2);
    init(point*2+1, (s+e)/2+1, e);
}
void propogate(int point){
    tree[point]+=lazy[point];
    lazy[point*2]+=lazy[point];
    lazy[point*2+1]+=lazy[point];
    lazy[point]=0;
}
void alter(int point, int s, int e, int a, int b, LL qu){
    if(a<=s&&e<=b){
        lazy[point]+=qu;
        return;
    }
    if(s>b||e<a)return;
    propogate(point);
    alter(point*2, s, (s+e)/2, a, b, qu);
    alter(point*2+1, (s+e)/2+1, e, a, b, qu);
    tree[point]=min(tree[point*2]+lazy[point*2], tree[point*2+1]+lazy[point*2+1]);
}
bool poss(int num){
    vector<pair<pil, pii> > query;
    vector<int> idy;
    query.pb(mp(mp(1, 0), mp(1, m-num)));
    query.pb(mp(mp(n-num+1, 0), mp(1, m-num)));
    idy.pb(1);
    idy.pb(m-num);
    for(int i=1; i<=p; i++){
        int sx=max(rect[i].F.F.F-num, 1);
        int ex=rect[i].F.S.F;
        int sy=max(rect[i].F.F.S-num, 1);
        int ey=min(rect[i].F.S.S, m-num);
        query.pb(mp(mp(sx, rect[i].S), mp(sy, ey)));
        query.pb(mp(mp(ex+1, -rect[i].S), mp(sy, ey)));
        idy.pb(sy);
        idy.pb(ey);
        if(sy>1)idy.pb(sy-1);
        if(ey<m-num)idy.pb(ey+1);
    }
    sortvec(idy);
    compress(idy);
    sortvec(query);
    init(1, 1, idy.size());
    for(auto &i:query){
        i.S.F=lower_bound(all(idy), i.S.F)-idy.begin()+1;
        i.S.S=lower_bound(all(idy), i.S.S)-idy.begin()+1;
    }
    for(int i=0; i<query.size(); i++){
        if(query[i].F.F>n-num)break;
        alter(1, 1, idy.size(), query[i].S.F, query[i].S.S, query[i].F.S);
        if(query[i].F.F!=query[i+1].F.F&&tree[1]+lazy[1]<=b)return true;
    }
    return false;
}
int main(){
    scanf("%d %d %lld %d", &n, &m, &b, &p);
    for(int i=1; i<=p; i++){
        scanf("%d %d %d %d %lld", &rect[i].F.F.F, &rect[i].F.F.S, &rect[i].F.S.F, &rect[i].F.S.S, &rect[i].S);
    }
    int l=0, r=min(n, m);
    while(l<r){
        int mid=(l+r)/2+1;
        if(poss(mid-1))l=mid;
        else r=mid-1;
    }
    printf("%d", l);
}

Compilation message

pyramid_base.cpp: In function 'bool poss(int)':
pyramid_base.cpp:70:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<query.size(); i++){
                  ~^~~~~~~~~~~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld %d", &n, &m, &b, &p);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d %lld", &rect[i].F.F.F, &rect[i].F.F.S, &rect[i].F.S.F, &rect[i].F.S.S, &rect[i].S);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 528 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 640 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 640 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 768 KB Output is correct
2 Correct 26 ms 640 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 640 KB Output is correct
2 Correct 15 ms 512 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1536 KB Output is correct
2 Correct 94 ms 1656 KB Output is correct
3 Correct 91 ms 1528 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 4684 KB Output is correct
2 Correct 431 ms 4732 KB Output is correct
3 Correct 346 ms 4704 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 6024 KB Output is correct
2 Correct 54 ms 3840 KB Output is correct
3 Correct 195 ms 8060 KB Output is correct
4 Correct 512 ms 8120 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 8568 KB Output is correct
2 Correct 775 ms 8564 KB Output is correct
3 Correct 254 ms 5560 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 446 ms 7004 KB Output is correct
2 Correct 1037 ms 9060 KB Output is correct
3 Correct 1040 ms 9060 KB Output is correct
4 Correct 1038 ms 9072 KB Output is correct
5 Correct 1082 ms 9048 KB Output is correct
6 Correct 242 ms 6068 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5101 ms 65320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5104 ms 87696 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5102 ms 97628 KB Time limit exceeded
2 Halted 0 ms 0 KB -