oj.uz

Submission #993512

# Submission time Handle Problem Language Result Execution time Memory
993512 2024-06-05T21:48:50 Z wood Sails (IOI07_sails) C++17
100 / 100
 363 ms 6236 KB 
#include <bits/stdc++.h>  
using namespace std;
 
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay

struct segtree
{
    int size = 1, ops[(int)1e6] = {0};
    segtree(int n){while(size<n) size*=2;}
    void upd(int l, int r){
        upd(l,r,0,0,size);
    }
    void upd(int l, int r, int x, int lx, int rx) {
        if(lx>=r||rx<=l) return;
        if(lx>=l&&rx<=r){
            ops[x]++;
            return; 
        }
        int m = (rx+lx)/2;
        upd(l,r,2*x+1,lx,m);
        upd(l,r,2*x+2,m,rx);
    }

    int get(int i){
        return get(i,0,0,size);
    }
    int get(int i, int x, int l, int r){
        if(r-l==1) return ops[x];
        int m = (r+l)/2;
        if(i<m) return get(i,2*x+1,l,m)+ops[x];
        else return get(i,2*x+2,m,r)+ops[x];
    }
};


int main()
{
    fast_cin();
    #ifndef ONLINE_JUDGE
        #ifdef _WIN32
            freopen("input.in", "r", stdin);
            freopen("input.out", "w", stdout);
        #endif
    #endif
    int n; cin>>n;
    p32 arr [n];
    for(p32 & sub : arr){
        cin>>sub.fi>>sub.se;
    }
    sort(arr,arr+n);
    segtree sgt(1e5);
    for (size_t i = 0; i < n; i++)
    {
        int left = arr[i].fi-arr[i].se;
        int l = -1, r = arr[i].fi;
        while(r-l>1){
            int m = (r+l)/2;
            if(sgt.get(m)>=sgt.get(left)) l = m;
            else r = m;
        }
        int done = 0;
        if(r<arr[i].fi){
            sgt.upd(r,arr[i].fi);
            done = arr[i].fi - r;
        }
        l = -1, r = arr[i].fi;
        while(r-l>1){
            int m = (r+l)/2;
            if(sgt.get(m)>sgt.get(left)) l = m;
            else r = m;
        }
        sgt.upd(r,r-done+arr[i].se);
    }
    ll res = 0;
    for (size_t i = 0; i < 1e5; i++)
    {
        ll x = sgt.get(i);
        res+=x*(x-1)/2;
    }
    cout<<res<<'\n';
    return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:71:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4188 KB Output is correct
2 Correct 8 ms 4364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4444 KB Output is correct
2 Correct 7 ms 4188 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4400 KB Output is correct
2 Correct 11 ms 4188 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4444 KB Output is correct
2 Correct 75 ms 4700 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 4700 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 5272 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 5972 KB Output is correct
2 Correct 224 ms 5724 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 5980 KB Output is correct
2 Correct 183 ms 5724 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 6236 KB Output is correct
2 Correct 177 ms 5976 KB Output is correct