| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 283887 |
2020-08-26T08:46:53 Z |
문홍윤(#5764) |
도로 건설 사업 (JOI13_construction) |
C++17 |
|
534 ms |
186124 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(x.begin(), x.end())
#define press(x) x.erase(unique(x.begin(), x.end()), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
const LL llinf=4e14;
int n, m, q;
pair<pii, int> p[200010];
pair<pii, pii> rct[200010];
pair<pil, int> qu[500010];
vector<int> idx, idy;
int tox[600010], toy[600010];
void compress_grid(){
svec(idx); svec(idy);
press(idx); press(idy);
for(int i=1; i<=n; i++){
int tmp=lower_bound(all(idx), p[i].F.F)-idx.begin()+1;
tox[tmp]=p[i].F.F;
p[i].F.F=tmp;
tmp=lower_bound(all(idy), p[i].F.S)-idy.begin()+1;
toy[tmp]=p[i].F.S;
p[i].F.S=tmp;
}
for(int i=1; i<=m; i++){
int tmp=lower_bound(all(idx), rct[i].F.F)-idx.begin()+1;
tox[tmp]=rct[i].F.F;
rct[i].F.F=tmp;
tmp=lower_bound(all(idx), rct[i].S.F)-idx.begin()+1;
tox[tmp]=rct[i].S.F;
rct[i].S.F=tmp;
tmp=lower_bound(all(idy), rct[i].F.S)-idy.begin()+1;
toy[tmp]=rct[i].F.S;
rct[i].F.S=tmp;
tmp=lower_bound(all(idy), rct[i].S.S)-idy.begin()+1;
toy[tmp]=rct[i].F.S;
rct[i].S.S=tmp;
}
}
struct LAZY_SEGMENT_TREE{
LL tree[2400010], lazy[2400010];
void prop(int point, int s, int e){
tree[point]+=lazy[point]*(e-s+1);
if(s!=e){
lazy[point*2]+=lazy[point];
lazy[point*2+1]+=lazy[point];
}
lazy[point]=0;
}
void eat(int point, int s, int e){
int mid=(s+e)/2;
tree[point]=tree[point*2]+tree[point*2+1];
tree[point]+=lazy[point*2]*(mid-s+1);
tree[point]+=lazy[point*2+1]*(e-mid);
}
void alter(int point, int s, int e, int a, int b, LL val){
if(e<a||s>b)return;
if(a<=s&&e<=b){
lazy[point]+=val;
return;
}
prop(point, s, e);
alter(point*2, s, (s+e)/2, a, b, val);
alter(point*2+1, (s+e)/2+1, e, a, b, val);
eat(point, s, e);
}
LL query(int point, int s, int e, int a, int b){
if(e<a||s>b)return 0;
if(a<=s&&e<=b)return tree[point]+lazy[point]*(e-s+1);
prop(point, s, e);
LL ret=0;
ret+=query(point*2, s, (s+e)/2, a, b);
ret+=query(point*2+1, (s+e)/2+1, e, a, b);
eat(point, s, e);
return ret;
}
void cl(){
memset(tree, 0, sizeof tree);
memset(lazy, 0, sizeof lazy);
}
}seg;
int e;
pair<LL, pii> edg[1000010];
vector<pii> vc[600010], upd[600010];
void make_edge(){
sort(p+1, p+n+1);
for(int i=1; i<=n+2*m; i++){
vc[i].clear();
upd[i].clear();
}
seg.cl();
for(int i=2; i<=n; i++){
if(p[i-1].F.F==p[i].F.F)vc[p[i].F.F].eb(i-1, i);
}
for(int i=1; i<=m; i++){
upd[rct[i].F.F].eb(rct[i].F.S, rct[i].S.S);
upd[rct[i].S.F+1].eb(-rct[i].F.S, -rct[i].S.S);
}
for(int i=1; i<=n+2*m; i++){
for(auto j:upd[i]){
if(j.F>0)seg.alter(1, 1, n+2*m, j.F, j.S, 1);
else seg.alter(1, 1, n+2*m, -j.F, -j.S, -1);
}
for(auto j:vc[i]){
LL tmp=seg.query(1, 1, n+2*m, p[j.F].F.S, p[j.S].F.S);
if(tmp)continue;
edg[++e]=mp((LL)(toy[p[j.S].F.S]-toy[p[j.F].F.S]), mp(p[j.F].S, p[j.S].S));
}
}
}
LL mst[200010];
struct UNION_FIND{
int par[200010];
UNION_FIND(){for(int i=1; i<=200000; i++)par[i]=i;}
int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}
void mergepar(int a, int b){par[findpar(a)]=findpar(b);}
}uf;
void make_mst(){
sort(edg+1, edg+e+1);
for(int i=1; i<=n-1; i++)mst[i]=llinf;
int num=n;
for(int i=1; i<=e; i++){
int a=edg[i].S.F, b=edg[i].S.S;
a=uf.findpar(a);
b=uf.findpar(b);
if(a==b)continue;
num--;
mst[num]=mst[num+1]+edg[i].F;
}
}
struct DYNAMIC_LI_CHAO{
struct NODE {
LL st, fin;
LL a, b;
NODE *l, *r;
NODE(){st=fin=a=0, b=llinf; l=r=0;}
}*root;
LL getfx(NODE* nd, LL num){
if(num<=(nd->fin+nd->st)/2)return min(nd->a*num+nd->b, nd->l?getfx(nd->l, num):llinf);
return min(nd->a*num+nd->b, nd->r?getfx(nd->r, num):llinf);
}
void in_LICHAO(NODE* nd, LL aa, LL bb){
LL mid=(nd->fin+nd->st)/2;
LL fr=nd->a*nd->st+nd->b;
LL re=nd->a*nd->fin+nd->b;
LL nfr=aa*nd->st+bb;
LL nre=aa*nd->fin+bb;
if(fr<=nfr&&re<=nre)return;
if(fr>=nfr&&re>=nre){
nd->a=aa;
nd->b=bb;
return;
}
if(!nd->l){
nd->l=new NODE;
nd->l->st=nd->st;
nd->l->fin=mid;
}
if(!nd->r){
nd->r=new NODE;
nd->r->st=mid+1;
nd->r->fin=nd->fin;
}
in_LICHAO(nd->l, aa, bb);
in_LICHAO(nd->r, aa, bb);
}
LL getfx(LL a){return getfx(root, a);}
void in(LL a, LL b){in_LICHAO(root, a, b);}
DYNAMIC_LI_CHAO(){root=new NODE; root->st=1ll, root->fin=1000000000ll;}
}li;
LL ans[500010];
void cht(){
sort(qu+1, qu+q+1);
int pv=1;
for(int i=1; i<=q; i++){
for(; pv<=n; pv++){
if(pv>qu[i].F.F)break;
li.in((LL)pv, mst[pv]);
}
ans[qu[i].S]=li.getfx(qu[i].F.S);
}
}
int main(){
scanf("%d %d %d", &n, &m, &q);
for(int i=1; i<=n; i++){
scanf("%d %d", &p[i].F.F, &p[i].F.S);
idx.eb(p[i].F.F);
idy.eb(p[i].F.S);
p[i].S=i;
}
for(int i=1; i<=m; i++){
scanf("%d %d %d %d", &rct[i].F.F, &rct[i].F.S, &rct[i].S.F, &rct[i].S.S);
idx.eb(rct[i].F.F);
idx.eb(rct[i].S.F);
idy.eb(rct[i].F.S);
idy.eb(rct[i].S.S);
}
for(int i=1; i<=q; i++){
scanf("%lld %d", &qu[i].F.S, &qu[i].F.F);
qu[i].S=i;
}
compress_grid();
make_edge();
for(int i=1; i<=n; i++)swap(p[i].F.F, p[i].F.S);
for(int i=1; i<=m; i++){
swap(rct[i].F.F, rct[i].F.S);
swap(rct[i].S.F, rct[i].S.S);
while(rct[i].F.F>rct[i].S.F);
while(rct[i].F.S>rct[i].S.S);
}
for(int i=1; i<=n+2*m; i++)swap(tox[i], toy[i]);
make_edge();
for(int i=1; i<=n; i++)swap(p[i].F.F, p[i].F.S);
for(int i=1; i<=m; i++){
swap(rct[i].F.F, rct[i].F.S);
swap(rct[i].S.F, rct[i].S.S);
}
for(int i=1; i<=n+2*m; i++)swap(tox[i], toy[i]);
make_mst();
cht();
for(int i=1; i<=q; i++)printf("%lld\n", ans[i]>=llinf?-1:ans[i]);
return 0;
}
Compilation message
construction.cpp: In function 'int main()':
construction.cpp:199:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
199 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:201:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
201 | scanf("%d %d", &p[i].F.F, &p[i].F.S);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:207:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
207 | scanf("%d %d %d %d", &rct[i].F.F, &rct[i].F.S, &rct[i].S.F, &rct[i].S.S);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:214:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
214 | scanf("%lld %d", &qu[i].F.S, &qu[i].F.F);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
67960 KB |
Output is correct |
| 2 |
Correct |
475 ms |
90280 KB |
Output is correct |
| 3 |
Correct |
481 ms |
90640 KB |
Output is correct |
| 4 |
Runtime error |
534 ms |
186124 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
67960 KB |
Output is correct |
| 2 |
Correct |
475 ms |
90280 KB |
Output is correct |
| 3 |
Correct |
481 ms |
90640 KB |
Output is correct |
| 4 |
Runtime error |
534 ms |
186124 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
67960 KB |
Output is correct |
| 2 |
Correct |
475 ms |
90280 KB |
Output is correct |
| 3 |
Correct |
481 ms |
90640 KB |
Output is correct |
| 4 |
Runtime error |
534 ms |
186124 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
67960 KB |
Output is correct |
| 2 |
Correct |
475 ms |
90280 KB |
Output is correct |
| 3 |
Correct |
481 ms |
90640 KB |
Output is correct |
| 4 |
Runtime error |
534 ms |
186124 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
