#3042
Pasionat de informatică și de puzzle-uri, Dorel a construit o matrice A de dimensiunea N × M lipind mai multe piese dreptunghiulare de diferite dimensiuni. Fiecare piesă este compusă din elemente de dimensiunea 1 × 1 și rețin o aceeași valoare (vezi exemplele). Matricea rezultată nu are spații libere, iar piesele din care este compusă nu se suprapun. Nu există două piese cu aceeași valoare.
Deși inițial părea că acest design este unul inedit, nu a durat mult până când Dorel s-a plictisit. Astfel, acum el dorește să “upgradeze” matricea construită. Dorel alege o submatrice delimitată de coordonatele (x1,y1) – colțul stânga-sus, (x2,y2) – colțul dreapta-jos (1 ≤ x1 ≤ x2 ≤ N, 1 ≤ y1 ≤ y2 ≤ M), unde crește toate valorile elementelor submatricei cu valoarea V.
Dorel efectuează în ordine Q operații de upgrade, operații numerotate de la 1 la Q. La finalizarea celor Q operații de upgrade, toate elementele din matrice au valoarea mai mare sau egală cu K. După o operație de upgrade, structura inițială a matricei se modifică.
Cerința
Cum priceperea lui Dorel este proverbială, trebuie să îl ajutați în rezolvarea următoarelor cerințe:
1) determinarea coordonatelor piesei cu număr maxim de elemente înainte ca Dorel să efectueze operațiile de upgrade;
2) determinarea numărului minim de operații de upgrade după care toate elementele matricei au valoarea mai mare sau egală cu K.
Date de intrare
Datele de intrare se citesc din fișierul amat.in, care are următoarea structură:
- pe prima linie se află numărul natural
C, care poate fi egal cu1sau2, în funcție de cerința ce trebuie rezolvată; - pe linia următoare se află două numerele naturale
NșiMcu semnificația din enunț; - pe următoarele
Nlinii se găsesc elementele matriceiA. - dacă
C = 2atunci fișierul de intrare mai conține: pe liniaN+2numerele naturaleQ Kcu semnificațiile din enunț; pe următoareleQlinii descrierea submatricelor asupra cărora se efectuează operații de upgrade de forma:x1 y1 x2 y2 V.
Date de ieșire
Datele de ieșire se vor scrie în fișierul amat.out, astfel:
Dacă C = 1 se vor scrie, separate prin spațiu patru numere naturale nenule x1 y1 x2 y2 ce reprezintă coordonatele colțului stânga-sus, respectiv colțului dreapta-jos unde este plasată piesa cu număr maxim de elemente înainte de upgrade. Dacă există mai multe astfel de piese, atunci vor fi scrise coordonatele piesei pentru care coordonatele colțului stânga-sus are valoarea liniei cea mai mare, iar la linii egale, se va alege piesa cu coordonata coloanei cea mai mare.
Dacă C = 2 se va scrie numărul natural nenul NR ce reprezintă numărului minim de operații de upgrade după care toate elementele matricei au valoarea mai mare sau egală cu K.
Restricții și precizări
2 ≤ N, M ≤ 1000;1 ≤ Q ≤ 100.000;1 ≤ V ≤ 1000-1000 ≤ elementele matricei A înainte de upgrade ≤ 1000- Operațiile de upgrade se efectuează obligatoriu în ordinea citirii
- Pentru teste în valoare de
30de puncte,C = 1 - Pentru teste în valoare de
30de puncte,C = 2şiN, M, Q ≤ 250 - Pentru teste în valoare de
50de puncte,C = 2şiQ ≤ 4000 - Pentru teste în valoare de
70de puncte,C = 2.
Exemplul 2:
amat.in
2 4 6 1 1 1 3 2 2 1 1 1 3 2 2 6 4 4 4 2 2 6 4 4 4 5 7 3 6 1 1 3 3 5 1 2 4 6 5 4 1 4 3 1
amat.out
2
Explicație
Se rezolvă cerința 2. Matricea inițială construită este cea prezentată mai sus.
Dorel efectuează 3 operații de upgrade.
Matricea obținută după efectuarea primului upgrade:6 6 6 3 2 26 6 6 3 2 211 9 9 4 2 26 4 4 4 5 7
Matricea obținută după efectuarea celui de-al doilea upgrade:6 11 11 8 7 76 11 11 8 7 711 14 14 9 7 76 9 9 9 10 12
Matricea obținută după efectuarea celui de-al treilea upgrade:6 11 11 8 7 76 11 11 8 7 711 14 14 9 7 77 10 10 9 10 12
La final tuturor operațiilor de upgrade, matricea are toate valorile mai mari sau egale 6.
Se observă că sunt suficiente primele două operații de upgrade pentru că toate elementele matricei să fie mai mari sau egale cu 6.
#include <fstream>
using namespace std;
ifstream cin("amat.in");
ofstream cout("amat.out");
struct coord
{
int x;
int y;
};
int c, n, m, a[1010][1010], maxi, elmaxi, smen[1010][1010], s[1010][1010], ok, x;
int q, k, l1, c1, l2, c2, v, i, j, f[2020], opv[100100], in, upgrade, sol, baza;
coord lefttop[2020], rightdown[2020];
coord op1[100100], op2[100100];
int main()
{
cin >> c >> n >> m;
if (c == 1)
{
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
cin >> a[i][j];
a[i][j] += 1000;
f[a[i][j]]++;
if (f[a[i][j]] == 1)
{
lefttop[a[i][j]].x = i;
lefttop[a[i][j]].y = j;
}
rightdown[a[i][j]].x = i;
rightdown[a[i][j]].y = j;
if (f[a[i][j]] >= maxi)
{
maxi = f[a[i][j]];
elmaxi = a[i][j];
}
}
}
cout << lefttop[elmaxi].x << ' ' << lefttop[elmaxi].y << ' ';
cout << rightdown[elmaxi].x << ' ' << rightdown[elmaxi].y;
}
else
{
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
cin >> a[i][j];
cin >> q >> k;
for (i = 1; i <= q; i++)
{
cin >> l1 >> c1 >> l2 >> c2 >> v;
opv[i] = v;
op1[i].x = l1;
op1[i].y = c1;
op2[i].x = l2;
op2[i].y = c2;
}
ok = 1;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
if (a[i][j] < k)
{
ok = 0;
j = m + 1;
i = n + 1;
}
}
}
if (ok)
cout << 0;
else
{
upgrade = 1;
while (upgrade <= q)
//upgrade <<= 1;
upgrade=upgrade*2;
//upgrade >>= 1;
upgrade=upgrade/2;
while (upgrade)
{
if (baza + upgrade <= q)
{
if (in < baza + upgrade)
{
for (i = in + 1; i <= baza + upgrade; i++)
{
v = opv[i];
l1 = op1[i].x;
c1 = op1[i].y;
l2 = op2[i].x;
c2 = op2[i].y;
smen[l1][c1] += v;
smen[l1][c2+1] -= v;
smen[l2+1][c1] -= v;
smen[l2+1][c2+1] += v;
}
}
else if (in > baza + upgrade)
{
for (i = in; i > baza + upgrade; i--)
{
v = opv[i];
l1 = op1[i].x;
c1 = op1[i].y;
l2 = op2[i].x;
c2 = op2[i].y;
smen[l1][c1] -= v;
smen[l1][c2+1] += v;
smen[l2+1][c1] += v;
smen[l2+1][c2+1] -= v;
}
}
in = baza + upgrade;
ok = 1;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + smen[i][j];
x = s[i][j] + a[i][j];
if (x < k)
{
ok = 0;
j = m + 1;
i = n + 1;
}
}
}
if (!ok)
{
baza += upgrade;
sol = baza;
}
}
//upgrade >>= 1;
upgrade=upgrade/2;
}
cout << sol + 1;
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main() {
ifstream cin("amat.in");
ofstream cout("amat.out");
int task; cin >> task;
int n, m; cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
cin >> a[i][j];
}
}
if (task == 1) {
const int kMax = 5000;
vector<int> lt(kMax, -1), rt(kMax, -1), up(kMax, -1), dw(kMax, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
int val = a[i][j] + 2000;
if (lt[val] == -1 || lt[val] > j) lt[val] = j;
if (rt[val] == -1 || rt[val] < j) rt[val] = j;
if (up[val] == -1 || up[val] > i) up[val] = i;
if (dw[val] == -1 || dw[val] < i) dw[val] = i;
}
}
tuple<int, int, int, int> best = make_tuple(-1, -1, -1, -1);
for (int i = 0; i < kMax; ++i) {
tuple<int, int, int, int> now = make_tuple(
(rt[i] - lt[i] + 1) * (dw[i] - up[i] + 1), up[i], lt[i], i);
best = max(best, now);
}
int col = get<3>(best);
cout << up[col] + 1 << " " << lt[col] + 1 << " " << dw[col] + 1 << " " << rt[col] + 1 << endl;
} else {
int q, k; cin >> q >> k;
vector<tuple<int, int, int, int, int>> ops;
for (int i = 0; i < q; ++i) {
int u, l, d, r, x; cin >> u >> l >> d >> r >> x;
ops.emplace_back(u, l, d, r, x);
}
int sol = 0;
for (int step = 1, adv = 1; step; adv ? step *= 2 : step /= 2) {
if (sol + step > q) { adv = 0; }
else {
vector<vector<int>> mars(n + 1, vector<int>(m + 1, 0));
for (int i = sol; i < sol + step; ++i) {
int u, l, d, r, x; tie(u, l, d, r, x) = ops[i];
mars[u - 1][l - 1] += x;
mars[u - 1][r] -= x;
mars[d][l - 1] -= x;
mars[d][r] += x;
}
bool bad = false;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (i > 0) mars[i][j] += mars[i - 1][j];
if (j > 0) mars[i][j] += mars[i][j - 1];
if (i > 0 && j > 0) mars[i][j] -= mars[i - 1][j - 1];
if (mars[i][j] + a[i][j] < k) {
bad = true;
}
}
}
/*
cerr << sol + step << endl;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j)
cerr << a[i][j] + mars[i][j] << " ";
cerr << endl;
}
*/
if (!bad) { adv = 0; continue; }
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
a[i][j] += mars[i][j];
}
}
sol += step;
}
}
assert(sol < q);
cout << sol + 1 << endl;
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
ifstream f("amat.in");
ofstream g("amat.out");
struct submatrix {
int x1, y1, x2, y2;
int k;
}ap[2003];
struct qry{
int x1, y1, x2, y2, w;
} Q[100001];
const int NM = 1002;
int a[NM][NM], A[NM][NM];
int B[NM][NM];
int n, m, q, c, K;
bool verif(int nr)
{
int x1, y1, x2, y2, w, x;
memset(A, 0, sizeof(A));
for(int i = 1; i <= nr; ++i){
x1 = Q[i].x1; y1 = Q[i].y1;
x2 = Q[i].x2; y2 = Q[i].y2;
w = Q[i].w;
A[x1][y1] += w;
A[x1][y2 + 1] -= w;
A[x2 + 1][y1] -= w;
A[x2 + 1][y2 + 1] += w;
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j) {
A[i][j] = A[i][j] + A[i-1][j] + A[i][j-1] - A[i-1][j-1];
x = A[i][j] + a[i][j];
if (x < K) return 0;
}
return 1;
}
int main()
{
int i, j, x, x1, y1, x2, y2;
f >> c >> n >> m;
for(i = 1; i <= n; ++i)
for(j = 1; j <= m; ++j)
f >> a[i][j];
if (c == 1){
for(i = 0; i <= 2000; ++i)
ap[i].y1 = ap[i].x1 = 2003;
for(i = 1; i <= n; ++i)
for(j = 1; j <= m; ++j) {
x = a[i][j];
x += 1000;
ap[x].x1 = min(ap[x].x1, i);
ap[x].y1 = min(ap[x].y1, j);
ap[x].x2 = max(ap[x].x2, i);
ap[x].y2 = max(ap[x].y2, j);
ap[x].k++;
}
int Max_arie = 0;
for(i = 0; i <= 2000; ++i)
if (ap[i].k > Max_arie) {
Max_arie = ap[i].k;
x1 = ap[i].x1;
x2 = ap[i].x2;
y1 = ap[i].y1;
y2 = ap[i].y2;
} else if (ap[i].k == Max_arie) {
if (ap[i].x1 > x1 || ap[i].x1 == x1 && ap[i].y1 > y1) {
x1 = ap[i].x1;
x2 = ap[i].x2;
y1 = ap[i].y1;
y2 = ap[i].y2;
}
}
g << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
} else {
f >> q >> K;
for(i = 1; i <= q; ++i) {
f >> x1 >> y1 >> x2 >> y2 >> x;
Q[i] = {x1, y1, x2, y2, x};
}
i = 1, j = q;
while (i <= j) {
int mij = (i+j) >> 1;
int k = verif(mij);
if (k) j = mij - 1;
else i = mij + 1;
}
g << i << "\n";
}
return 0;
}