oj.uz

Submission #332914

# Submission time Handle Problem Language Result Execution time Memory
332914 2020-12-04T01:37:32 Z vkgainz Sails (IOI07_sails) C++17
35 / 100
 266 ms 3812 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 get(int i, int x=0, int lx=0, int rx=sz) { //smallest color which has occurence strictly greater than k times
    prop(x, lx, rx);
    if(rx-lx==1)
        return seg[x];
    int m = (lx+rx)/2;
    if(i<m) 
        return get(i, 2*x+1, lx, m);
    else 
        return get(i, 2*x+2, m, rx);
}
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 col = get(h-k);
        if(col==0) {
            upd(0, k);
        }
        else {
            int cmp = get(h-k-1);
            if(cmp==col) {
                int x = numLess(0, h, col-1);
                upd(h-x, h);
                int left = k-x;
                int y = numLess(0, h, col);
                upd(h-y, h-y+left);
            }
            else {
                upd(h-k, h);
            }
        }
    }
    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:74:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     int n; scanf("%d",&n);
      |            ~~~~~^~~~~~~~~
sails.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   78 |         scanf("%d%d",&mast[i].f,&mast[i].s);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3044 KB Output is correct
2 Incorrect 5 ms 3192 KB Output isn't 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3044 KB Output is correct
2 Incorrect 7 ms 3044 KB Output isn't correct

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 3556 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 230 ms 3556 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 3812 KB Output is correct
2 Incorrect 65 ms 3684 KB Output isn't correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 266 ms 3812 KB Output isn't correct
2 Halted 0 ms 0 KB -