oj.uz

답안 #487967

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
487967 2021-11-17T09:46:10 Z David_M 사탕 분배 (IOI21_candies) C++17
0 / 100
 5000 ms 31352 KB 
#include "candies.h"
#include <bits/stdc++.h>
#define vi vector<int>
#define sz(x) (x).size()
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define pii pair<int, int>
#define vpii vector<pii>
#define pb push_back
using namespace std;
//////cout
const int N=1000006, INF=1e9 + 7;
int n, m, lazy[4*N];


//struct aaa{int mx, mn, mxi, mni;} T[4*N], o={0,INF,-1,-1};
pair<pii,pii> T[4*N], o={{0, -1}, {INF, -1}};


void push(int x){
    lazy[x<<1  ]+=lazy[x];
    lazy[x<<1|1]+=lazy[x];
    T[x].F.F+=lazy[x];
    T[x].S.F+=lazy[x];
    lazy[x]=0;
}

void build(int L=0, int R=n, int x=1){
    if(L==R){
        T[x]={{0, L}, {0, L}};
        return;
    }
    int m=L+R>>1;
    build(L, m, x<<1);
    build(m+1, R, x<<1|1);
    auto xl=T[x<<1], xr=T[x<<1|1];
    T[x]={max(xl.F, xr.F), min(xl.S, xr.S)};
}

void upd(int l, int r, int val, int L=0, int R=n, int x=1){
    if(R<l || L>r)return;
    if(L>=l && R<=r){
        lazy[x]+=val;
        return;
    }
    int m=L+R>>1;
    push(x);
    upd(l, r, val, L, m, x<<1);
    upd(l, r, val, m+1, R, x<<1|1);

    push(x<<1); push(x<<1|1);
    auto xl=T[x<<1], xr=T[x<<1|1];
    T[x]={max(xl.F, xr.F), min(xl.S, xr.S)};
}

pair<pii,pii> getmaxmin(int l, int r, int L=0, int R=n, int x=1){
    if(R<l || L>r)return o;
    push(x);
    if(L>=l && R<=r){
        return T[x];
    }
    int m=L+R>>1;
    auto [mx1, mn1] = getmaxmin(l, r, L, m, x<<1);
    auto [mx2, mn2] = getmaxmin(l, r, m+1, R, x<<1|1);
    return {max(mx1, mx2), min(mn1, mn2)};
}

int get(int i, int L=0, int R=n, int x=1){
    push(x);
    if(L==R)return T[x].F.F;
    int m=L+R>>1;
    if(m>=i){
        return get(i, L, m, x<<1);
    }else{
        return get(i, m+1, R, x<<1|1);
    }
}

int solve(int c){
    int l=0, r=n, d, u, dval, uval, g=0;


    while(l<=r){

        for (int i=0; i<=n; i++){
            pair<pii,pii> y=getmaxmin(i, i);
            //cout<<i<<" "<<get(i)<<" "<<y.F.F<<" "<<y.F.S<<" "<<y.S.F<<" "<<y.S.S<<endl;
        }//cout<<endl;

        int m=l+r>>1;
        auto [mx,mn] = getmaxmin(m, n);
        //cout<<"AAA"<<m<<" "<<mx.F<<" "<<mx.S<<" "<<mn.F<<" "<<mn.S<<endl;
        if(mx.F-mn.F<c)r=m-1;
        else{
            g=1;
            dval=mn.F; d=mn.S;
            uval=mx.F; u=mx.S;
            l=m+1;
        }
    }
    if(!g)return get(n);
    //cout<<d<<" "<<u<<endl;
    if(d<u){
        return c-(get(u)-get(n));
    }else{
        return get(n)-get(d);
    }
}

vi distribute_candies(vi c, vi l, vi r, vi v) {
    m = sz(c), n=sz(l);
    vi ans(n);
    vpii a[m+1];
    build();
    for (int i=0; i<n; i++){
        a[l[i]  ].pb({v[i],i});
        a[r[i]+1].pb({v[i],i});
    }
    set<pii> s;
    for (int i=0; i<m; i++){

        for (auto [val,t]:a[i]){
            if(s.find({val,t})!=s.end()){
                s.erase({val,t});
                upd(t+1, n, -val);
            }else{
                s.insert({val,t});
                upd(t+1, n, val);
            }
        }
        //cout<<"AAA"<<endl;
        for(auto [x,y]:s)//cout<<x<<" "<<y<<endl;
        //cout<<endl;
        ans[i]=solve(c[i]);
    }
    return ans;
}
/*
main(){


}
*/

Compilation message

candies.cpp: In function 'void build(int, int, int)':
candies.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int m=L+R>>1;
      |           ~^~
candies.cpp: In function 'void upd(int, int, int, int, int, int)':
candies.cpp:47:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int m=L+R>>1;
      |           ~^~
candies.cpp: In function 'std::pair<std::pair<int, int>, std::pair<int, int> > getmaxmin(int, int, int, int, int)':
candies.cpp:63:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int m=L+R>>1;
      |           ~^~
candies.cpp: In function 'int get(int, int, int, int)':
candies.cpp:72:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int m=L+R>>1;
      |           ~^~
candies.cpp: In function 'int solve(int)':
candies.cpp:87:27: warning: variable 'y' set but not used [-Wunused-but-set-variable]
   87 |             pair<pii,pii> y=getmaxmin(i, i);
      |                           ^
candies.cpp:91:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |         int m=l+r>>1;
      |               ~^~
candies.cpp:81:25: warning: variable 'dval' set but not used [-Wunused-but-set-variable]
   81 |     int l=0, r=n, d, u, dval, uval, g=0;
      |                         ^~~~
candies.cpp:81:31: warning: variable 'uval' set but not used [-Wunused-but-set-variable]
   81 |     int l=0, r=n, d, u, dval, uval, g=0;
      |                               ^~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:133:18: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  133 |         for(auto [x,y]:s)//cout<<x<<" "<<y<<endl;
      |                  ^~~~~

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5037 ms 31352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Runtime error 3 ms 412 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -