oj.uz

Submission #1092362

# Submission time Handle Problem Language Result Execution time Memory
1092362 2024-09-23T21:51:56 Z MrPavlito Sails (IOI07_sails) C++17
0 / 100
 1000 ms 13360 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 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)
    {
        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);
    if(seg[nod<<1|1] <= seg[nod<<1])
    {
        update(nod<<1|1, mid+1, tr,l,r,nm);
        update(nod<<1, tl, mid,l,r,nm);
    }
    else
    {
        update(nod<<1, tl, mid,l,r,nm);
        update(nod<<1|1, mid+1, tr,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);
        }
        sort(all(niz));
        //for(int i=0; i<n; i++)cout << niz[i].fi << " " << niz[i].sc << endl;
        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

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: In function 'void get(long long int, long long int, long long int, long long int)':
sails.cpp:82:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int mid = tl+tr>>1;
      |               ~~^~~
sails.cpp: In function 'int main()':
sails.cpp:109:17: warning: unused variable 'preveal' [-Wunused-variable]
  109 |             int preveal = p;
      |                 ^~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10584 KB Output is correct
2 Incorrect 3 ms 10588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 10648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 10588 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 237 ms 10584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 11356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 11932 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1028 ms 12632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1012 ms 12888 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 13360 KB Time limit exceeded
2 Halted 0 ms 0 KB -