oj.uz

Submission #746981

# Submission time Handle Problem Language Result Execution time Memory
746981 2023-05-23T10:35:48 Z grogu The Potion of Great Power (CEOI20_potion) C++14
56 / 100
 3000 ms 77528 KB 
#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define fi first
#define sc second
#define pll pair<ll,ll>
#define endl '\n'
#define all(a) a.begin(),a.end()
#define llinf 1000000000
#define si(a) (ll)(a.size())
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

using namespace std;
#define maxn 200005
ll n,d,m;
vector<pll> t[2*maxn];
map<pll,ll> mp;
ll ls[2*maxn],rs[2*maxn],tsz,root = 0;
ll a[maxn];
void init(int N, int D, int H[]) {
	n = N;
	d = D;
	for(ll i = 1;i<=n;i++){
		a[i] = H[i-1];
	}
}
void init(ll &v,ll tl,ll tr){
    if(!v) v = ++tsz;
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
}
void upd(ll v,ll tl,ll tr,ll l,ll r,pll p){
    if(tl>tr||tl>r||l>r||l>tr) return;
    if(tl>=l&&tr<=r){t[v].pb(p);return;}
    ll mid = (tl+tr)/2;
    upd(ls[v],tl,mid,l,r,p);
    upd(rs[v],mid+1,tr,l,r,p);
}
pll f(pll p){return {min(p.fi,p.sc),max(p.fi,p.sc)};}
map<pll,bool> tu;
void curseChanges(int U, int A[], int B[]) {
    m = U;
    init(root,0,m);
    for(ll i = 0;i<m;i++){
        ll x = A[i],y = B[i];
        x++; y++;
        pll p = f({x,y});
        if(!tu[p]){
            mp[p] = i+1;
            tu[p] = 1;
        }else{
            upd(root,0,m,mp[p],i,{x,y});
            upd(root,0,m,mp[p],i,{y,x});
            tu[p] = 0;
        }
    }
    for(auto it : mp){
        if(tu[it.fi]){
            pll p = it.fi;
            ll x = p.fi,y = p.sc;
            upd(root,0,m,it.sc,m,{x,y});
            upd(root,0,m,it.sc,m,{y,x});
        }
    }
    for(ll i = 1;i<=tsz;i++) sort(all(t[i]));
}
bool cmp(ll x,ll y){return a[x]<a[y];}
vector<ll> vx,vy;
ll get(vector<pll> &v,ll x){
    ll l = 0,r = v.size()-1,rez = -1,mid;
    while(l<=r){
        mid = (l+r)/2;
        if(v[mid].fi>=x) rez = mid,r = mid-1;
        else l = mid+1;
    }
    return rez;
}
void get(ll v,ll tl,ll tr,ll id,ll x,ll y){
    ll i = get(t[v],x);
    if(i!=-1){
        for(ll j = i;j<t[v].size();j++){
            if(t[v][j].fi!=x) break;
            vx.pb(t[v][j].sc);
        }
    }
    i = get(t[v],y);
    if(i!=-1){
        for(ll j = i;j<t[v].size();j++){
            if(t[v][j].fi!=y) break;
            vy.pb(t[v][j].sc);
        }
    }
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    if(id<=mid) get(ls[v],tl,mid,id,x,y);
    else get(rs[v],mid+1,tr,id,x,y);
}
ll reshi(vector<ll> c,vector<ll> b){
    ll j = 0;
    ll ans = llinf;
    for(ll i = 0;i<si(c);i++){
        while(j<=si(b)-1&&a[b[j]]<a[c[i]]) j++;
        if(j==si(b)) break;
        ans = min(ans,a[b[j]]-a[c[i]]);
    }
    return ans;
}
int question(int x, int y, int j) {
    x++; y++;
    vx.clear();
    vy.clear();
    get(root,0,m,j,x,y);
    sort(all(vx),cmp);
    sort(all(vy),cmp);
    return min(reshi(vx,vy),reshi(vy,vx));
}
/**
6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4 26
3 0 8 0
0 5 5 1000000000
3 0 11 14
*/

Compilation message

potion.cpp: In function 'void get(int, int, int, int, int, int)':
potion.cpp:84:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(ll j = i;j<t[v].size();j++){
      |                      ~^~~~~~~~~~~~
potion.cpp:91:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for(ll j = i;j<t[v].size();j++){
      |                      ~^~~~~~~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9936 KB Output is correct
2 Correct 8 ms 9936 KB Output is correct
3 Correct 7 ms 9936 KB Output is correct
4 Correct 19 ms 10656 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1055 ms 77416 KB Output is correct
2 Correct 943 ms 77384 KB Output is correct
3 Correct 385 ms 37904 KB Output is correct
4 Correct 2141 ms 68484 KB Output is correct
5 Correct 1139 ms 76608 KB Output is correct
6 Execution timed out 3064 ms 61580 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 970 ms 77528 KB Output is correct
2 Correct 1397 ms 48772 KB Output is correct
3 Correct 1348 ms 61564 KB Output is correct
4 Correct 1778 ms 61472 KB Output is correct
5 Correct 1064 ms 77464 KB Output is correct
6 Correct 1921 ms 61768 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 13000 KB Output is correct
2 Correct 134 ms 11696 KB Output is correct
3 Correct 153 ms 10912 KB Output is correct
4 Correct 911 ms 12292 KB Output is correct
5 Correct 931 ms 12984 KB Output is correct
6 Correct 180 ms 12880 KB Output is correct
7 Correct 715 ms 11408 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9680 KB Output is correct
2 Correct 8 ms 9936 KB Output is correct
3 Correct 8 ms 9936 KB Output is correct
4 Correct 7 ms 9936 KB Output is correct
5 Correct 19 ms 10656 KB Output is correct
6 Correct 1055 ms 77416 KB Output is correct
7 Correct 943 ms 77384 KB Output is correct
8 Correct 385 ms 37904 KB Output is correct
9 Correct 2141 ms 68484 KB Output is correct
10 Correct 1139 ms 76608 KB Output is correct
11 Execution timed out 3064 ms 61580 KB Time limit exceeded
12 Halted 0 ms 0 KB -