oj.uz

Submission #1092641

# Submission time Handle Problem Language Result Execution time Memory
1092641 2024-09-24T16:26:39 Z MrPavlito Sails (IOI07_sails) C++17
100 / 100
 727 ms 9308 KB 
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define pii pair<int,int>

using namespace std;

const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
vector<int> seg(MAXN<<2,-1);
vector<int> lazy(MAXN<<2, 0);
int rez;

void push(int nod, int tl, int tr)
{
    if(lazy[nod] == 0) return;
    if(tl != tr)
    {
        lazy[nod<<1] += lazy[nod];
        lazy[nod<<1|1] += lazy[nod];
    }
    seg[nod] += lazy[nod];
    lazy[nod] = 0;
}

int query(int nod, int tl, int tr, int l, int r)
{
    push(nod, tl, tr);
    if(tl > r || tr < l || tl > tr) return -inf;
    if(tl >= l && tr <= r) return seg[nod];
    int mid = tl + tr >> 1;
    return max(query(nod<<1, tl, mid, l, r), query(nod<<1|1, mid + 1, tr, l, r));
}

void update(int nod, int tl, int tr, int l, int r)
{
    push(nod, tl, tr);
    if(tl > r || tr < l || tl > tr || l > r) return;
    if(tl >= l && tr <= r)
    {
        lazy[nod]++;
        push(nod, tl, tr);
        return;
    }
    int mid = tl + tr >> 1;
    update(nod<<1, tl, mid, l, r);
    update(nod<<1|1, mid + 1, tr, l, r);
    seg[nod] = max(seg[nod<<1], seg[nod<<1|1]);
}


signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int tt = 1;
    while(tt--)
    {
        int n;
        cin >> n;
        vector<pii> niz(n);
        int mx = MAXN;
        for(int i = 0; i < n; i++)
        {
            cin >> niz[i].fi >> niz[i].sc;
        }

        sort(all(niz));
        //for(auto x: niz)cout << x.fi << " " << x.sc << endl;
        for(int i = 0; i < n; i++)
        {
            int trazi = niz[i].fi- niz[i].sc;
            int p = query(1, 1, mx, trazi, trazi);
            int tr = niz[i].sc;
            int lb = 1;
            int l = 1; int r = trazi;
            while(l <= r)
            {
                int mid = l + r >> 1;
                if(query(1, 1, mx, mid, mid) == p)
                {
                    lb = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            l = trazi;
            r = niz[i].fi;
            int ub = trazi;
            while(l <= r)
            {
                int mid = l + r >> 1;
                if(query(1, 1, mx, mid, mid) == p)
                {
                    ub = mid;
                    l = mid + 1;
                }
                else r = mid - 1;
            }
            if(ub == niz[i].fi)update(1,1,mx, lb, lb+tr-1);
            else
            {
                update(1, 1, mx, ub+1, niz[i].fi);
                tr-=(niz[i].fi-ub);
                update(1,1,mx, lb, lb+tr-1);
            }

        }
        int finalrez = 0;
        for(int j = 1; j <= mx; j++)
        {
           int p = query(1,1,mx, j,j);
            finalrez += (p) * (p + 1) / 2;
        }
        cout << finalrez << endl;
    }
}

Compilation message

sails.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
sails.cpp:36:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
sails.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
sails.cpp:50:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
sails.cpp: In function 'int main()':
sails.cpp:83:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |                 int mid = l + r >> 1;
      |                           ~~^~~
sails.cpp:96:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |                 int mid = l + r >> 1;
      |                           ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6492 KB Output is correct
2 Correct 20 ms 6732 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6492 KB Output is correct
2 Correct 19 ms 6488 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 6716 KB Output is correct
2 Correct 19 ms 6492 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6492 KB Output is correct
2 Correct 24 ms 6744 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 6744 KB Output is correct
2 Correct 27 ms 6748 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 6900 KB Output is correct
2 Correct 154 ms 7260 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 7516 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 7780 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 8576 KB Output is correct
2 Correct 511 ms 8536 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 9044 KB Output is correct
2 Correct 331 ms 8796 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 727 ms 9052 KB Output is correct
2 Correct 567 ms 9308 KB Output is correct