# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
288576 | 2020-09-01T16:16:10 Z | MasterTaster | Quality Of Living (IOI10_quality) | C++14 | 1 ms | 512 KB |
#include<bits/stdc++.h> #include <stdio.h> #include <stdlib.h> #include "quality.h" using namespace std; #define ll long long #define pb push_back #define pii pair<int, int> #define xx first #define yy second #define endl "\n" #define MAXN 9000000 static int R,C,H,W,Q[3001][3001],i,j,ans; int pref[3010][3010], q[3010][3010], pom[3010][3010]; //int bit[310]; int pola; /*pair<int, int> pos[90010]; ll sum(int x) { ll ret=0; while (x) { ret+=bit[x]; x-=x&(-x); } return ret; } void upd(int x, int val) { while (x<MAXN) { bit[x]+=val; x+=x&(-x); } return; }*/ bool check(int med) { for (int i=0; i<R; i++) { for (int j=0; j<C; j++) { pref[i][j]=0; pom[i][j]=(q[i][j]<=med) ? 1 : 0; ///cout<<pom[i][j]<<" "; } ///cout<<endl; } ///cout<<endl; for (int i=0; i<R; i++) { for (int j=0; j<C; j++) { pref[i][j]=pom[i][j]; if (i>0) pref[i][j]+=pref[i-1][j]; if (j>0) pref[i][j]+=pref[i][j-1]; if (i>0 && j>0) pref[i][j]-=pref[i-1][j-1]; ///cout<<pref[i][j]<<" "; } ///cout<<endl; } for (int i=H-1; i<R; i++) { for (int j=W-1; j<C; j++) { int koliko=pref[i][j]; if (i>=H) koliko-=pref[i-H][j]; if (j>=W) koliko-=pref[i][j-W]; if (i>=H && j>=W) koliko+=pref[i-H][j-W]; if (koliko>=pola) { /*cout<<med<<" "<<i<<" "<<j<<" "<<koliko<<endl;*/ return true; } } } return false; } int rectangle(int R, int C, int H, int W, int Q[3001][3001]) { pola=H*W/2+1; for (int i=0; i<R; i++) for (int j=0; j<C; j++) q[i][j]=Q[i][j]; int l=1, r=R*C; ll ress=-1; while (l<=r) { int mid=l+(r-l)/2; ///cout<<mid<<":"<<endl<<endl<<endl; if (check(mid)) { ress=mid; r=mid-1; } else l=mid+1; } return ress; /*int ress=R*C+1; int koji=H*W/2+1; for (int i=0; i<R; i++) for (int j=0; j<C; j++) pos[Q[i][j]]={i, j}; for (int i=0; i<=R-H; i++) { for (int k=i; k<i+H; k++) for (int j=0; j<W; j++) { cout<<Q[k][j]<<" "; upd(Q[k][j], 1); } cout<<endl; for (int j=0; j<=C-W; j++) { int l=1, r=R*C; int trRess=1000000000; while (l<=r) { int mid=l+(r-l)/2; if (sum(mid)>=koji) { trRess=mid; r=mid-1; } else l=mid+1; } cout<<"ee "<<trRess<<endl; ress=min(trRess, ress); for (int k=i; k<i+H; k++) { upd(Q[k][j], -1); if (j+W<C) upd(Q[k][j+W], 1); } } } return ress;*/ //return 1; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |