Submission #1092635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092635		MrPavlito	Sails (IOI07_sails)	C++17	15 / 100	659 ms	9308 KiB

sails

#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 = 0;
        for(int i = 0; i < n; i++)
        {
            cin >> niz[i].fi >> niz[i].sc;
            mx = max(mx, niz[i].fi);
        }

        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+1;
            int p = query(1, 1, mx, trazi, trazi);
            int tr = niz[i].sc;
            int lb = niz[i].fi;
            int l = 1; int r = niz[i].fi;
            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 = 1;
            r = niz[i].fi;
            int ub = r;
            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 (stderr)

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:84:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |                 int mid = l + r >> 1;
      |                           ~~^~~
sails.cpp:97:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |                 int mid = l + r >> 1;
      |                           ~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 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