Submission #793468

#	Time	Username	Problem	Language	Result	Execution time	Memory
793468		idiotcomputer	Sails (IOI07_sails)	C++11	100 / 100	172 ms	5764 KiB

sails

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100001;
const int MIN_V = -1;
const int MAX_V = MAX_N+1;

int gmin[4*MAX_N+1];
int gmax[4*MAX_N+1];

void upd(int l, int r, int idx, int t, int c, bool which){
    if (l > t || r < t){
        return;
    }
    if (l == r){
        if (which){
            gmin[idx] = c;
        } else{
            gmax[idx] = c;
        }
        return;
    }
    
    int m = (l+r)/2;
    upd(l,m,2*idx+1,t,c,which);
    upd(m+1,r,2*idx+2,t,c,which);
    
    if (which){
        gmin[idx] = min(gmin[2*idx+1],gmin[2*idx+2]);
    } else {
        gmax[idx] = max(gmax[2*idx+1],gmax[2*idx+2]);
    }
    return;
}

int query(int l, int r, int idx, int tl, int tr, bool which){
    if (l > tr || r < tl){
        if (which){
            return MAX_V;
        } else {
            return MIN_V;
        }
    }
    if (l >= tl && r <= tr){
        if (which){
            return gmin[idx];
        } else {
            return gmax[idx];
        }
    }
    
    int m = (l+r)/2;
    int r1 = query(l,m,2*idx+1,tl,tr,which);
    int r2 = query(m+1,r,2*idx+2,tl,tr,which);
    if (which){
        return min(r1,r2);
    } else {
        return max(r1,r2);
    }
}

void updv(vector<int> &vals, int a, int c){
    if (c == 1){
        vals[a] += 1;
        if (vals[a] == 0){
            upd(0,MAX_N-1,0,a,MAX_V,true);
            upd(0,MAX_N-1,0,a,MIN_V,false);
        } else if (vals[a] == 1){
            upd(0,MAX_N-1,0,a,a,true);
            upd(0,MAX_N-1,0,a,a,false);
        }
    } else if (c == -1){
        vals[a] -= 1;
        if (vals[a] == -1){
            upd(0,MAX_N-1,0,a,a,true);
            upd(0,MAX_N-1,0,a,a,false);
        } else if (vals[a] == 0){
            upd(0,MAX_N-1,0,a,MAX_V,true);
            upd(0,MAX_N-1,0,a,MIN_V,false);
        }
    }    
}

int main()
{
    //memset(gmin,MAX_V,sizeof(gmin));
    //memset(gmax,MIN_V,sizeof(gmax));
    for (int i =0; i < 4*MAX_N+1; i++){
        gmin[i] = MAX_V;
        gmax[i] = MIN_V;
    }
    int n;
    cin >> n;
    
    vector<pair<int,int>> all(n);
    for (int i =0; i < n; i++){
        cin >> all[i].first >> all[i].second;
    }
 //   cout << "\n\n";
    sort(all.begin(),all.end());
   /* for (int i =0; i < n; i++){
    cout << all[i].first << " " << all[i].second << '\n';
    }*/
    vector<int> vals(MAX_N);
    for (int i =0; i < n; i++){
        int ch = all[i].first;
        int ck = all[i].second;
        int nidx = ch - ck;
      /*  
        cout << '\n' << i << ": " << ch << " " << ck << " " << nidx << '\n';
                for (int i =0; i < 7; i++){
            cout << vals[i] << " ";
        }
        cout << '\n';*/
        if (vals[nidx] != 0){
            updv(vals,ch,-1);
            updv(vals,nidx,1);
            continue;
        }
        
        //in a level group
        int a = query(0,MAX_N-1,0,0,nidx,false);
        int b = query(0,MAX_N-1,0,nidx,MAX_N-1,true);
        if (a == MIN_V){
            a = 0;
        } 
        if (b == MAX_V){
            b = ch;
        }
      //  cout << a << ", " << b <<'\n';
        updv(vals,a,1);
        if (a+b-nidx < ch){
            updv(vals,a+b-nidx,-1);
        } else if (b >= ch){
            updv(vals,ch,-1);
        }
        if (b < ch){
            updv(vals,ch,-1);
            updv(vals,b,1);
        }

    }
    //cout << "DONE\n";
    long long int tot = 0;
    int curr = 0;
     /*     for (int i =0; i < 7; i++){
            cout << vals[i] << " ";
        }
        cout << '\n';*/
    for (int i = 0; i < MAX_N; i++){
        curr += vals[i];
      /*  if (curr != 0){
            cout << i << ", " << curr << '\n';
        }*/
        tot += (long long int) curr * (curr - 1) / 2;
    }
    cout << tot << '\n';
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10