USACO: Shaping Regions

Блог пользователя KBakozoda

Автор KBakozoda, 13 лет назад, По-русски

Кто-нибудь можете помочь с этой задачей? Есть какие-нибудь идеи для её решения? (У самого есть одна идея , но её реализация на С++ составит примерно 200-250 строк..может есть идеи по-лучше)

Спасибо.

usaco, problem, help

KBakozoda
13 лет назад
5

Комментарии (5)

Написать комментарий?

yeputons

13 лет назад, скрыть # |

По сути требуется структура, которая умеет быстрее квадрата делать присваивание на отрезке и за разумное время выгружать все данные в массив. Двумерное дерево отрезков такими способностями, как я знаю, не обладает.

Зато можно применить массив размера A из одномерных деревьев отрезков. Запрос будет обрабатываться за $\text{[math]}$ , что вполне приемлимо. Если сделать сжатие координат, то точно зайдёт (возможно, если попихать, то с ним зайдёт и квадрат)

→ Ответить

BackendDeveloper

12 лет назад, скрыть # ^ |

Сможешь объяснить как именно сжатие координат надо сделать?

→ Ответить

yeputons

12 лет назад, скрыть # ^ |

Смогу, но не могу открыть условие — регистрацию просят, а она не помогает.

Сжатие координат — это какой-то такой код:

vector<int> xs(n), ys(n);
vector<pair<int, int> > pts(n);
for (int i = 0; i < n; i++) {
  scanf("%d%d", &pts[i].first, &pts[i].second);
  xs[i] = pts[i].first;
  ys[i] = pts[i].second;
}
sort(xs.begin(), xs.end());
xs.erase(  unique(xs.begin(), xs.end()),  xs.end());

sort(ys.begin(), ys.end());
ys.erase(  unique(ys.begin(), ys.end()),  ys.end());

for (int i = 0; i < n; i++) {
  pts[i].first  = lower_bound(xs.begin(), xs.end(), pts[i].first ) - xs.begin();
  pts[i].second = lower_bound(ys.begin(), ys.end(), pts[i].second) - ys.begin();
}

Теперь точки у нас имеют координаты от 0 до n - 1, а относительный порядок сохранился. Чтобы сделать запрос к [L, R] в исходных координатах, надо сделать запрос от lower_bound(xs.begin(), xs.end(), L) - xs.begin() до upper_bound(xs.begin(), xs.end(), R) - xs.begin() - 1 (включительно)

→ Ответить

BackendDeveloper

12 лет назад, скрыть # ^ |

На USACO Memory limit.

Попытался сдать ту же задачу на тимусе. 1147.Цветная Бумага.

Wrong Answer 7.

/*
 ID: seidazi1
 PROG: rect1
 LANG: C++
*/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

using namespace std;

bool u[10001][33000];
short a[10001][33000];
int ans[2501];

int sz;

void push(int k,int v){
 if(u[k][v]){
  if(v<sz){
   u[k][v*2]=u[k][v*2+1]=1;
   a[k][v*2]=a[k][v*2+1]=a[k][v];
  }
  u[k][v]=0;
 }
}

void upd(int k,int v,int L,int R,int l,int r,int color){
 push(k,v);
 if(R<l || L>r) return;
 if(l<=L && R<=r){
  u[k][v]=1; a[k][v]=color;
  push(k,v); return;
 }
 upd(k,v*2,L,(L+R)/2,l,r,color);
 upd(k,v*2+1,(L+R)/2+1,R,l,r,color);
}

void check(int k, int v, int L,int R, int l,int r){
 if(R<l || L>r) return;
 if(u[k][v] || L==R){
  ans[a[k][v]] += R-L+1;

  /*
  for(int e=L;e<=R;e++)
   fprintf(stderr, "%d", a[k][v]);
  */

  return;
 }
 check(k, v*2, L,(L+R)/2, l,r);
 check(k, v*2+1, (L+R)/2+1,R, l,r); 
}

int k,n,m,cnt,i;
int lx[1000],ly[1000],rx[1000],ry[1000],col[1000]; 

int main(){

 scanf("%d %d %d", &n,&m,&cnt);
 for(i=0;i<cnt;i++){
  scanf("%d %d %d %d %d", &lx[i],&ly[i], &rx[i],&ry[i], &col[i]);
  lx[i]++; ly[i]++; rx[i]++; ry[i]++;
 }

 for(sz=1; sz<m; sz*=2);
             
 for(i=1;i<=n;i++)
  upd(i, 1, 1,sz, 1,m, 1);

 for(i=0;i<cnt;i++){
  for(k=ly[i];k<ry[i];k++){
   if(lx[i] < rx[i])
    upd(k, 1, 1,sz, lx[i],rx[i]-1, col[i]);
  }
 }

 for(i=1;i<=n;i++){ 
  check(i, 1, 1,sz, 1,m);
  // fprintf(stderr, "\n");
 }

 printf("%d %d\n", 1,ans[1]);

 sort(col,col+cnt);

 for(i=0;i<cnt;i++){
  if(i && col[i-1]==col[i]) 
   continue;
  if(col[i]!=1 && ans[col[i]])
   printf("%d %d\n", col[i],ans[col[i]]);
 }

 return 0;
}

Не могли бы сказать в чем ошибка?

→ Ответить

yeputons

12 лет назад, скрыть # ^ |

Рекомендую убирать длинный код на pastebin.com, а то читать неудобно.
Проверьте ограничения. Например, в коде явно должно быть либо ограничение на координаты, либо их сжатие. Ни того, ни другого я с ходу не увидел.

→ Ответить