Submission #1092578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092578		MrPavlito	Sails (IOI07_sails)	C++17	10 / 100	346 ms	9304 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]);
}

void get(int nod, int tl, int tr, int index)
{
    push(nod, tl, tr);
    rez = min(rez, seg[nod]);
    if(tl == tr) return;
    int mid = tl + tr >> 1;
    if(index <= mid) get(nod<<1, tl, mid, index);
    else get(nod<<1|1, mid + 1, tr, index);
}

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 p = query(1, 1, mx, 1, niz[i].fi);
            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;
                rez = -1;
                if(query(1, 1, mx, 1, mid) == p)
                {
                    lb = mid;
                    r = mid - 1;
                }
                else l = mid + 1;
            }
            int pomoc = tr - lb + 1;
            update(1, 1, mx, 1, lb - 1);
            update(1, 1, mx, niz[i].fi - pomoc + 1, niz[i].fi);
            /*
            for(int j = 1; j <= mx; j++)
            {
                rez = inf;
                get(1, 1, mx, j);
                cout << rez << " ";
            }
            cout << endl;
            */
        }
        int finalrez = 0;
        for(int j = 1; j <= mx; j++)
        {
            rez = inf;
            get(1, 1, mx, j);
            finalrez += (rez) * (rez + 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 'void get(long long int, long long int, long long int, long long int)':
sails.cpp:61:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
sails.cpp: In function 'int main()':
sails.cpp:92:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |                 int mid = l + r >> 1;
      |                           ~~^~~

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