Submission #233193

#TimeUsernameProblemLanguageResultExecution timeMemory
233193dualityTreatment Project (JOI20_treatment)C++11
100 / 100
1209 ms174760 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- struct pro { int t,l,r,c; }; bool comp(pro a,pro b) { return a.t < b.t; } pro p[100000]; vpii adjList[3000000]; pii sorted[100000]; int bit[100001],num; LLI dist[3000000]; priority_queue<pair<LLI,int> > H; int main() { int i; int N,M; scanf("%d %d",&N,&M); for (i = 0; i < M; i++) scanf("%d %d %d %d",&p[i].t,&p[i].l,&p[i].r,&p[i].c),p[i].l--,p[i].r--; sort(p,p+M,comp); int j; for (i = 0; i < M; i++) { if (p[i].l == 0) adjList[0].pb(mp(i+2,p[i].c)); if (p[i].r == N-1) adjList[i+2].pb(mp(1,0)); sorted[i] = mp(p[i].l-p[i].t,i); } num = M+2; sort(sorted,sorted+M); for (i = 1; i <= M; i++) bit[i] = num++; for (i = 0; i < M; i++) { int x = lower_bound(sorted,sorted+M,mp(p[i].l-p[i].t,i))-sorted; for (j = x+1; j <= M; j += j & (-j)) { adjList[num].pb(mp(bit[j],0)),adjList[num].pb(mp(i+2,p[i].c)); bit[j] = num++; } x = upper_bound(sorted,sorted+M,mp(p[i].r-p[i].t+1,M))-sorted-1; for (j = x+1; j > 0; j -= j & (-j)) adjList[i+2].pb(mp(bit[j],0)); } for (i = 0; i < M; i++) sorted[i] = mp(p[i].l+p[i].t,i); sort(sorted,sorted+M); for (i = 1; i <= M; i++) bit[i] = num++; for (i = M-1; i >= 0; i--) { int x = lower_bound(sorted,sorted+M,mp(p[i].l+p[i].t,i))-sorted; for (j = x+1; j <= M; j += j & (-j)) { adjList[num].pb(mp(bit[j],0)),adjList[num].pb(mp(i+2,p[i].c)); bit[j] = num++; } x = upper_bound(sorted,sorted+M,mp(p[i].r+p[i].t+1,M))-sorted-1; for (j = x+1; j > 0; j -= j & (-j)) adjList[i+2].pb(mp(bit[j],0)); } for (i = 0; i < num; i++) dist[i] = -1; dist[0] = 0,H.push(mp(0,0)); while (!H.empty()) { int u = H.top().second; LLI d = -H.top().first; H.pop(); if (d > dist[u]) continue; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i].first; if ((dist[v] == -1) || (dist[u]+adjList[u][i].second < dist[v])) { dist[v] = dist[u]+adjList[u][i].second; H.push(mp(-dist[v],v)); } } } printf("%lld\n",dist[1]); return 0; }

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:114:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~
treatment.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~~
treatment.cpp:72:90: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < M; i++) scanf("%d %d %d %d",&p[i].t,&p[i].l,&p[i].r,&p[i].c),p[i].l--,p[i].r--;
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...