제출 #132210

#제출 시각아이디문제언어결과실행 시간메모리
132210WannnabeIOI모임들 (IOI18_meetings)C++14
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> #include "meetings.h" using namespace std; #define X first #define Y second #define pb push_back #define ii pair<int, int>; typedef long long ll; const int maxn = 750005; int n, q; struct rng { int ed; ll m, b; rng(int _ed = 0, ll _m = 0, ll _b = 0) : ed(_ed), m(_m), b(_b){} ll eval(int x) { return m*x+b; } }; map<int, rng> png; int arr[maxn]; int st[4*maxn]; void build(int p = 1, int L = 0, int R = n-1) { if(L == R) { st[p] = L; return; } int M = (L+R)/2; build(2*p, L, M); build(2*p+1, M+1, R); if(arr[st[2*p]]>= arr[st[2*p+1]]) st[p] = st[2*p]; else st[p] = st[2*p+1]; } int rmq(int i, int j, int p = 1, int L = 0, int R = n-1) { if(i> R || j< L) return -1; if(i<= L && R<= j) return st[p]; int M = (L+R)/2; int x = rmq(i, j, 2*p, L, M); int y = rmq(i, j, 2*p+1, M+1, R); if(x == -1) return y; if(y == -1) return x; return (arr[x]>= arr[y])?x:y; } void build2(int p = 1, int L = 0, int R = n-1) { if(L == R) { st[p] = L; return; } int M = (L+R)/2; build2(2*p, L, M); build2(2*p+1, M+1, R); if(arr[st[2*p]]> arr[st[2*p+1]]) st[p] = st[2*p]; else st[p] = st[2*p+1]; } int rmq2(int i, int j, int p = 1, int L = 0, int R = n-1) { if(i> R || j< L) return -1; if(i<= L && R<= j) return st[p]; int M = (L+R)/2; int x = rmq2(i, j, 2*p, L, M); int y = rmq2(i, j, 2*p+1, M+1, R); if(x == -1) return y; if(y == -1) return x; return (arr[x]> arr[y])?x:y; } vector<int> tree[maxn]; vector<ii> ql[maxn]; vector<ii> qr[maxn]; ll ansl[maxn]; ll ansr[maxn]; int cartesian(int L, int R) { if(L> R) return -1; int u = rmq(L, R); int x = cartesian(L, u-1); int y = cartesian(u+1, R); if(x != -1) tree[u].pb(x); if(y != -1) tree[u].pb(y); return u; } int cartesian2(int L, int R) { if(L> R) return -1; int u = rmq2(L, R); int x = cartesian2(L, u-1); int y = cartesian2(u+1, R); if(x != -1) tree[u].pb(x); if(y != -1) tree[u].pb(y); return u; } pair<int, int> cov[maxn]; ll lz[maxn]; int sz[maxn]; int arx[maxn]; void solve(int u, vector<ii> *quest, ll *answ) { int lc = -1, rc = -1; if(tree[u].size() == 2) { lc = tree[u][0]; rc = tree[u][1]; } else if(tree[u].size() == 1) { if(tree[u][0]< u) lc = tree[u][0]; else rc = tree[u][0]; } cov[u] = {u, u}; if(lc != -1) { solve(lc, quest, answ); cov[u].X = min(cov[u].X, cov[lc].X); } if(rc != -1) { solve(rc, quest, answ); cov[u].Y = max(cov[u].Y, cov[rc].Y); } rng here; ll midcost; if(lc == -1) { midcost = arr[u]; } else { auto it = png.upper_bound(u); --it; midcost = arr[u]+(it->second).eval(u-1)+lz[lc]; } here = rng(u, 0, midcost); png[u] = here; // printf("midcost[%d] = %lld\n", u, midcost); // printf("solving %d\n", u); if(rc != -1) { ll add = 1LL*(u-cov[u].X+1)*arr[u]; lz[rc] += add; int st = u+1; bool fixed = false; while(st<= cov[u].Y) { // printf("%d\n", st); rng f2 = png[st]; int ed = f2.ed; rng f1 = rng(0, arr[u], midcost-1LL*arr[u]*u); if(f1.eval(ed)<= f2.eval(ed)+lz[rc]) { // printf("this case\n"); png.erase(st); st = ed+1; sz[rc]--; } else { // printf("bad at %d\n", st); int lo = st, hi = ed; while(lo< hi) { int mid = (lo+hi)/2; // printf("%d\n", mid); if(f1.eval(mid)<= f2.eval(mid)+lz[rc]) lo = mid+1; else hi = mid; } // printf("first to okay: %d\n", lo); png.erase(st); sz[rc]--; if(u+1<= lo-1) { png[u+1] = rng(lo-1, arr[u], midcost-1LL*arr[u]*u-lz[rc]); // printf("{%d, %d} left fuction\n", u+1, lo-1); sz[rc]++; } // else printf("WTF\n"); png[lo] = f2; sz[rc]++; fixed = true; break; } } // printf("fixed = %d\n", fixed); if(!fixed) { // printf("{%d, %d} left function\n", u+1, cov[u].Y); png[u+1] = rng(cov[u].Y, arr[u], midcost-1LL*arr[u]*u-lz[rc]); sz[rc]++; } } if(lc != -1 && rc != -1) { if(sz[lc]< sz[rc]) { int st = cov[u].X; while(st< u) { png[st].b += lz[lc]-lz[rc]; st = png[st].ed+1; } png[u].b -= lz[rc]; lz[u] = lz[rc]; } else { int st = u+1; while(st<= cov[u].Y) { png[st].b += lz[rc]-lz[lc]; st = png[st].ed+1; } png[u].b -= lz[lc]; lz[u] = lz[lc]; } } else if(lc != -1) { png[u].b -= lz[lc]; lz[u] = lz[lc]; } else { png[u].b -= lz[rc]; lz[u] = lz[rc]; } sz[u] = 1; if(lc != -1) sz[u] += sz[lc]; if(rc != -1) sz[u] += sz[rc]; for(auto kk : quest[u]) { int want = kk.X, id = kk.Y; auto it = png.upper_bound(want); --it; answ[id] = (it->second).eval(want)+lz[u]; } // printf("rangeL(%d) = %d\n", u, cov[u].X); // for(int i = cov[u].X; i<= cov[u].Y; i++) // { // auto it = png.upper_bound(i); // --it; // // printf("using %d\n", it->first); // printf("cost[rangeL(%d), %d] = %lld\n", u, i, (it->second).eval(i)+lz[u]); // } } vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R) { n = H.size(); q = L.size(); for(int i = 0; i< n; i++) arr[i] = H[i]; build(); int root = cartesian(0, n-1); for(int i = 0; i< q; i++) { int arg = rmq(L[i], R[i]); arx[i] = arg; if(arg+1<= R[i]) { int argr = rmq(arg+1, R[i]); qr[argr].pb(ii(R[i], i)); } if(L[i]<= arg-1) { int argl = rmq(L[i], arg-1); ql[n-argl-1].pb(ii(n-L[i]-1, i)); // printf("ql[%d] pb %d\n", n-argl-1, n-L[i]-1); } } // printf("finished\n"); solve(root, qr, ansr); memset(lz, 0, sizeof lz); memset(cov, 0, sizeof cov); memset(sz, 0, sizeof sz); for(int i = 0; i< n; i++) tree[i].clear(); png.clear(); for(int i = 0; i< n; i++) arr[i] = H[n-i-1]; build2(); root = cartesian2(0, n-1); solve(root, ql, ansl); for(int i = 0; i< n; i++) arr[i] = H[i]; vector<ll> ret(q); for(int i = 0; i< q; i++) { // printf("ansl[%d] = %lld, ansr[%d] = %lld\n", i, ansl[i], i, ansr[i]); ret[i] = min(ansl[i]+1LL*(R[i]-arx[i]+1)*arr[arx[i]], ansr[i]+1LL*(arx[i]-L[i]+1)*arr[arx[i]]); } return ret; }

컴파일 시 표준 에러 (stderr) 메시지

meetings.cpp:7:12: error: template argument 1 is invalid
 #define ii pair<int, int>;
            ^~~~~~~~~~~~~~
meetings.cpp:84:8: note: in expansion of macro 'ii'
 vector<ii> ql[maxn];
        ^~
meetings.cpp:7:12: error: template argument 2 is invalid
 #define ii pair<int, int>;
            ^~~~~~~~~~~~~~
meetings.cpp:84:8: note: in expansion of macro 'ii'
 vector<ii> ql[maxn];
        ^~
meetings.cpp:84:10: error: expected unqualified-id before '>' token
 vector<ii> ql[maxn];
          ^
meetings.cpp:7:12: error: template argument 1 is invalid
 #define ii pair<int, int>;
            ^~~~~~~~~~~~~~
meetings.cpp:85:8: note: in expansion of macro 'ii'
 vector<ii> qr[maxn];
        ^~
meetings.cpp:7:12: error: template argument 2 is invalid
 #define ii pair<int, int>;
            ^~~~~~~~~~~~~~
meetings.cpp:85:8: note: in expansion of macro 'ii'
 vector<ii> qr[maxn];
        ^~
meetings.cpp:85:10: error: expected unqualified-id before '>' token
 vector<ii> qr[maxn];
          ^
meetings.cpp:7:12: error: template argument 1 is invalid
 #define ii pair<int, int>;
            ^~~~~~~~~~~~~~
meetings.cpp:116:26: note: in expansion of macro 'ii'
 void solve(int u, vector<ii> *quest, ll *answ)
                          ^~
meetings.cpp:7:12: error: template argument 2 is invalid
 #define ii pair<int, int>;
            ^~~~~~~~~~~~~~
meetings.cpp:116:26: note: in expansion of macro 'ii'
 void solve(int u, vector<ii> *quest, ll *answ)
                          ^~
meetings.cpp:7:12: error: template argument 1 is invalid
 #define ii pair<int, int>;
            ^~~~~~~~~~~~~~
meetings.cpp:116:26: note: in expansion of macro 'ii'
 void solve(int u, vector<ii> *quest, ll *answ)
                          ^~
meetings.cpp:7:12: error: template argument 2 is invalid
 #define ii pair<int, int>;
            ^~~~~~~~~~~~~~
meetings.cpp:116:26: note: in expansion of macro 'ii'
 void solve(int u, vector<ii> *quest, ll *answ)
                          ^~
meetings.cpp:7:12: error: template argument 1 is invalid
 #define ii pair<int, int>;
            ^~~~~~~~~~~~~~
meetings.cpp:116:26: note: in expansion of macro 'ii'
 void solve(int u, vector<ii> *quest, ll *answ)
                          ^~
meetings.cpp:7:12: error: template argument 2 is invalid
 #define ii pair<int, int>;
            ^~~~~~~~~~~~~~
meetings.cpp:116:26: note: in expansion of macro 'ii'
 void solve(int u, vector<ii> *quest, ll *answ)
                          ^~
meetings.cpp:116:19: error: 'vector' is not a type
 void solve(int u, vector<ii> *quest, ll *answ)
                   ^~~~~~
meetings.cpp:116:25: error: expected ',' or '...' before '<' token
 void solve(int u, vector<ii> *quest, ll *answ)
                         ^
meetings.cpp:7:26: error: expected ')' before ';' token
 #define ii pair<int, int>;
                          ^
meetings.cpp:116:26: note: in expansion of macro 'ii'
 void solve(int u, vector<ii> *quest, ll *answ)
                          ^~
meetings.cpp:116:28: error: expected unqualified-id before '>' token
 void solve(int u, vector<ii> *quest, ll *answ)
                            ^
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:279:4: error: 'qr' was not declared in this scope
    qr[argr].pb(ii(R[i], i));
    ^~
meetings.cpp:279:4: note: suggested alternative: 'q'
    qr[argr].pb(ii(R[i], i));
    ^~
    q
meetings.cpp:7:26: error: expected primary-expression before ';' token
 #define ii pair<int, int>;
                          ^
meetings.cpp:279:16: note: in expansion of macro 'ii'
    qr[argr].pb(ii(R[i], i));
                ^~
meetings.cpp:279:27: error: expected ';' before ')' token
    qr[argr].pb(ii(R[i], i));
                           ^
meetings.cpp:284:4: error: 'ql' was not declared in this scope
    ql[n-argl-1].pb(ii(n-L[i]-1, i));
    ^~
meetings.cpp:284:4: note: suggested alternative: 'q'
    ql[n-argl-1].pb(ii(n-L[i]-1, i));
    ^~
    q
meetings.cpp:7:26: error: expected primary-expression before ';' token
 #define ii pair<int, int>;
                          ^
meetings.cpp:284:20: note: in expansion of macro 'ii'
    ql[n-argl-1].pb(ii(n-L[i]-1, i));
                    ^~
meetings.cpp:284:29: warning: value computed is not used [-Wunused-value]
    ql[n-argl-1].pb(ii(n-L[i]-1, i));
                       ~~~~~~^~
meetings.cpp:284:35: error: expected ';' before ')' token
    ql[n-argl-1].pb(ii(n-L[i]-1, i));
                                   ^
meetings.cpp:289:14: error: 'qr' was not declared in this scope
  solve(root, qr, ansr);
              ^~
meetings.cpp:289:14: note: suggested alternative: 'q'
  solve(root, qr, ansr);
              ^~
              q
meetings.cpp:300:14: error: 'ql' was not declared in this scope
  solve(root, ql, ansl);
              ^~
meetings.cpp:300:14: note: suggested alternative: 'q'
  solve(root, ql, ansl);
              ^~
              q