Submission #332915

#	Time	Username	Problem	Language	Result	Execution time	Memory
332915		vkgainz	Sails (IOI07_sails)	C++17	0 / 100	254 ms	3812 KiB

sails

#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, h);
        }
        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 (stderr)

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10