Submission #1092360

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092360		MrPavlito	Sails (IOI07_sails)	C++17	0 / 100	91 ms	13364 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 endl "\n"
#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> visine(MAXN);
vector<pii> seg(MAXN<<2, {-1,-1});
vector<int> lazy(MAXN<<2, 0);
int rez;
int p;

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].fi += lazy[nod];
    seg[nod].sc+= 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].fi;
    int mid = tl+tr>>1;
    return min(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, int&nm)
{
    push(nod, tl, tr);
    if(seg[nod].fi > p)return;
    if(nm <=0)return;
    if(tl > r)return;
    if(tr - tl+1 <= nm && seg[nod].fi == seg[nod].sc && seg[nod].fi == p)
    {
        nm-= (tr-tl+1);
        lazy[nod] ++;
        push(nod, tl, tr);
        return;
    }
    if(tl==tr)return;
    int mid = tl+tr>>1;
    push(nod<<1, tl, mid);
    push(nod<<1|1, mid+1, tr);
    int mn1 = seg[nod<<1].fi;
    int mn2 = seg[nod<<1|1].fi;

        update(nod<<1|1, mid+1, tr,l,r,nm);
        update(nod<<1, tl, mid,l,r,nm);
    seg[nod].fi = min(seg[nod<<1].fi,seg[nod<<1|1].fi);
    seg[nod].sc = max(seg[nod<<1].sc,seg[nod<<1|1].sc);
}

void get(int nod, int tl, int tr, int index)
{
    push(nod, tl, tr);
    rez = max(rez, seg[nod].fi);
    //cout << rez << endl;
    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;
    //cin >> tt;
    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);
        }
        for(int i=0; i<n; i++)
        {
            int tr = niz[i].sc;
            p = query(1, 1,mx, 1, niz[i].fi);
            int preveal = p;
            update(1,1,mx,1,niz[i].fi,tr);
            p++;
            if(tr>0)update(1,1,mx,1,niz[i].fi,tr);
        }
        int finalrez = 0;
         for(int j=1; j<=mx; j++)
        {
            rez = -1;
            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:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     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, long long int&)':
sails.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = tl+tr>>1;
      |               ~~^~~
sails.cpp:62:9: warning: unused variable 'mn1' [-Wunused-variable]
   62 |     int mn1 = seg[nod<<1].fi;
      |         ^~~
sails.cpp:63:9: warning: unused variable 'mn2' [-Wunused-variable]
   63 |     int mn2 = seg[nod<<1|1].fi;
      |         ^~~
sails.cpp: In function 'void get(long long int, long long int, long long int, long long int)':
sails.cpp:77:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |     int mid = tl+tr>>1;
      |               ~~^~~
sails.cpp: In function 'int main()':
sails.cpp:102:17: warning: unused variable 'preveal' [-Wunused-variable]
  102 |             int preveal = p;
      |                 ^~~~~~~

• 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: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10