oj.uz

Submission #332912

# Submission time Handle Problem Language Result Execution time Memory
332912 2020-12-04T01:25:19 Z vkgainz Sails (IOI07_sails) C++17
90 / 100
 1000 ms 4068 KB 
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//nlog^2n should work...?
const int MX = 1e5+20;
int seg[4*MX], lazy[4*MX];
int sz = 1;
void prop(int x, int lx, int rx) {
    seg[x]+=lazy[x];
    if(rx-lx!=1) {
        lazy[2*x+1]+=lazy[x];
        lazy[2*x+2]+=lazy[x];
    }
    lazy[x] = 0;
}
int numLess(int l, int r, int c, int x=0, int lx=0, int rx=sz) { //gets color with <= appear <=k times
    if(lx>=r || rx<=l) 
        return 0;
    prop(x, lx, rx);
    int m = (lx+rx)/2;
    if(lx>=l && rx<=r) {
        if(seg[x]<=c) 
            return rx-lx;
        else {
            if(rx-lx==1)
                return 0;
            prop(2*x+1, lx, m), prop(2*x+2, m, rx);
            if(seg[2*x+2]<=c)
                return rx-m+numLess(l, r, c, 2*x+1, lx, m);
            else
                return numLess(l, r, c, 2*x+2, m, rx);
        }
    }
    return numLess(l, r, c, 2*x+1, lx, m)+numLess(l, r, c, 2*x+2, m, rx);
}
void upd(int l, int r, int x=0, int lx=0, int rx=sz) { //add 1 to [l, r)
    prop(x, lx, rx);
    if(lx>=r || rx<=l) return;
    if(lx>=l && rx<=r) {
        ++seg[x];
        if(rx-lx!=1) {
            lazy[2*x+1]++;
            lazy[2*x+2]++;
        }
        return;
    }
    int m = (lx+rx)/2;
    upd(l, r, 2*x+1, lx, m), upd(l, r, 2*x+2, m, rx);
    seg[x] = max(seg[2*x+1], seg[2*x+2]);
}
vector<int> ret;
void push(int x=0, int lx=0, int rx=sz) {
    prop(x, lx, rx);
    if(rx-lx==1) {
        ret.push_back(seg[x]);
        return;
    }
    int m = (lx+rx)/2;
    push(2*x+1, lx, m);
    push(2*x+2, m, rx);
}
int main() {
    int n; scanf("%d",&n);
    while(sz<100005) sz*=2;
    vector<pair<int, int>> mast(n);
    for(int i=0;i<n;i++)
        scanf("%d%d",&mast[i].f,&mast[i].s);
    sort(mast.begin(), mast.end());
    for(int i=0;i<n;i++) {
        int h = mast[i].f;
        int k = mast[i].s;
        int lo = 0, hi = 100001;
        for(int j=0;j<17;j++) {
            int mid = (lo+hi)/2;
            if(numLess(0, h, mid)>k) {
                hi = mid;
            }
            else {
                lo = mid+1;
            }
        }
        int numIn = numLess(0, h, hi-1);
        upd(h-numIn, h);
        int numLeft = k-numIn;
        int start = h-numLess(0, h, hi);
        upd(start, start+numLeft);
    }
    push();
    long long ans = 0LL;
    //check for overflow
    for(int i=0;i<=100000;i++) {
        ans+=ret[i]*1LL*(ret[i]-1)/2;
    }
    printf("%lld\n",ans);
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:64:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |     int n; scanf("%d",&n);
      |            ~~~~~^~~~~~~~~
sails.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |         scanf("%d%d",&mast[i].f,&mast[i].s);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3044 KB Output is correct
2 Correct 4 ms 3044 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3044 KB Output is correct
2 Correct 4 ms 3044 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3044 KB Output is correct
2 Correct 4 ms 3044 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3044 KB Output is correct
2 Correct 8 ms 3044 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3044 KB Output is correct
2 Correct 12 ms 3044 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 3044 KB Output is correct
2 Correct 204 ms 3300 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 3300 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 3428 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 3704 KB Output is correct
2 Correct 857 ms 3684 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 672 ms 3972 KB Output is correct
2 Correct 613 ms 4068 KB Output is correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 3940 KB Output is correct
2 Execution timed out 1079 ms 1772 KB Time limit exceeded