Submission #613830

#	Time	Username	Problem	Language	Result	Execution time	Memory
613830		czhang2718	Constellation 3 (JOI20_constellation3)	C++17	Compilation error	0 ms	0 KiB

constellation3

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
#define f first
#define s second

const int N=2e5+1;
int c[N], x[N], y[N];
int n, m;
vector<int> xs;
int ind[N];
ll sum[N];
vector<pair<int,int>> pts;

struct segtree{
    int n;
    vector<pair<int,int>> mx;

    segtree(){
    }

    void init(int n, vector<int> &v){
        this->n=n;
        mx.resize(4*n);
        build(v, 0, 0, n);
    }

    void build(vector<int> &v, int x, int lx, int rx){
        if(rx-lx==1){
            mx[x]={v[lx],lx};
            cout << "max " << lx << " "<< rx << ' ' << mx[x].f << '\n';
            return;
        }
        int m=(lx+rx)/2;
        build(v, 2*x+1, lx, m);
        build(v, 2*x+2, m, rx);
        mx[x]=max(mx[2*x+1], mx[2*x+2]);
    }

    void pull(int i, int x, int lx, int rx){
        if(rx-lx==1){
            mx[x]={-1e9, i};
            return;
        }
        int m=(lx+rx)/2;
        if(i<m) pull(i, 2*x+1, lx, m);
        else pull(i, 2*x+2, m, rx);
        mx[x]=max(mx[2*x+1], mx[2*x+2]);
    }

    void pull(int i){ pull(i, 0, 0, n); }

    pair<int,int> get_max(int l, int r, int x, int lx, int rx){
        cout << x << endl;
        if(lx>=l && rx<=r) return mx[x];
        if(lx>=r || rx<=l) return {-1e9, 9};
        int m=(lx+rx)/2;
        return max(get_max(l, r, 2*x+1, lx, m), get_max(l, r, 2*x+2, m, rx));
    }

    pair<int,int> get_max(int l, int r){ return r<=l?make_pair(-int(1e9), 0):get_max(l, r, 0, 0, n); }
} star, pillar;

ll ft[N];

void upd(int i, ll v){
    i++;
    while(i<=n){
        ft[t]+=v;
        i+=i&-i;
    }
}

ll sum(int i){
    i++;
    ll ret=0;
    while(i){
        ret+=ft[i];
        i-=i&-i;
    }
}

ll sum(int l, int r){
    l++; r++;
    return sum(r)-sum(l-1);
}

ll solve(int l, int r){
    cout << "lr " << l << " " <<r << endl;
    if(r<l) return 0;
    vector<int> ind;

    pair<int,int> p=pillar.get_max(l, r+1);
    int mx=p.f;
    cout << "max! " << mx << " " << p.s << "\n";
    pillar.pull(p.s);
    ind.push_back(p.s);
    while((p=pillar.get_max(l, r+1)).f==mx){
        int j=p.s;
        pillar.pull(j);
        ind.push_back(j);
    }

    int L=lower_bound(xs.begin(), xs.end(), l)-xs.begin();
    int R=upper_bound(xs.begin(), xs.end(), r)-xs.begin();
    while((p=star.get_max(L, R)).f>mx){
        int j=p.s;
        int st=pts[j].s;
        star.pull(j);
        sum.upd(x[st], c[j]);
    }

    ll ret=1e18;

    int prv=l-1;
    ind.push_back(r+1);
    for(int i=0; i<ind.size(); i++){
        ret=min(ret, solve(prv+1, ind[i]-1));
        prv=ind[i];
    }
    cout << "solve " << l << " "<< r <<" " << ret << "\n";
    return ret;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    vector<int> h(n);
    for(int &x:h) cin >> x;
    pillar.init(n, h);

    ll tot=0;
    cin >> m;
    vector<int> ys;
    for(int i=0; i<m; i++){
        cin >> x[i] >> y[i] >> c[i];
        x[i]--;
        xs.push_back(x[i]);
        pts.push_back({x[i],i});
        tot+=c[i];
    }
    sort(pts.begin(), pts.end());
    sort(xs.begin(), xs.end());
    for(auto &p:pts) p.f=y[p.s], ys.push_back(p.f);
    star.init(m, ys); 

    cout << tot-solve(0,n-1);
}

Compilation message (stderr)

constellation3.cpp: In function 'void upd(int, ll)':
constellation3.cpp:70:12: error: 't' was not declared in this scope
   70 |         ft[t]+=v;
      |            ^
constellation3.cpp: At global scope:
constellation3.cpp:75:13: error: 'll sum(int)' redeclared as different kind of entity
   75 | ll sum(int i){
      |             ^
constellation3.cpp:13:4: note: previous declaration 'll sum [200001]'
   13 | ll sum[N];
      |    ^~~
constellation3.cpp: In function 'll sum(int)':
constellation3.cpp:82:1: warning: no return statement in function returning non-void [-Wreturn-type]
   82 | }
      | ^
constellation3.cpp: At global scope:
constellation3.cpp:84:20: error: 'll sum(int, int)' redeclared as different kind of entity
   84 | ll sum(int l, int r){
      |                    ^
constellation3.cpp:13:4: note: previous declaration 'll sum [200001]'
   13 | ll sum[N];
      |    ^~~
constellation3.cpp: In function 'll sum(int, int)':
constellation3.cpp:86:17: error: 'sum' cannot be used as a function
   86 |     return sum(r)-sum(l-1);
      |                 ^
constellation3.cpp:86:26: error: 'sum' cannot be used as a function
   86 |     return sum(r)-sum(l-1);
      |                          ^
constellation3.cpp: In function 'll solve(int, int)':
constellation3.cpp:111:13: error: request for member 'upd' in 'sum', which is of non-class type 'll [200001]' {aka 'long long int [200001]'}
  111 |         sum.upd(x[st], c[j]);
      |             ^~~
constellation3.cpp:118:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int i=0; i<ind.size(); i++){
      |                  ~^~~~~~~~~~~