oj.uz

Submission #793450

# Submission time Handle Problem Language Result Execution time Memory
793450 2023-07-25T21:35:10 Z idiotcomputer Sails (IOI07_sails) C++11
0 / 100
 138 ms 5740 KB 
#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 << i << ": " << ch << " " << ck << " " << nidx << '\n';
        updv(vals,ch,-1);
        if (vals[nidx] != 0){
            updv(vals,nidx,1);
            continue;
        }
        
        //in a level group
        int a = query(0,MAX_N-1,0,0,nidx,true);
        int b = query(0,MAX_N-1,0,nidx,MAX_N-1,false);
        if (a == MAX_V){
            a = 0;
        } 
        if (b == MIN_V){
            b = ch;
        }
    //    cout << a << ", " << b <<'\n';
        updv(vals,a,1);
        updv(vals,a+b-nidx,-1);
        updv(vals,b,1);
    }
    //cout << "DONE\n";
    long long int tot = 0;
    int curr = 0;
    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
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 5.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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