Submission #220629

#TimeUsernameProblemLanguageResultExecution timeMemory
220629_7_7_Sweeping (JOI20_sweeping)C++14
1 / 100
18170 ms1239460 KiB
#include <bits/stdc++.h> //#define int long long //#pragma GCC optimize("Ofast") //#pragma comment(linker, "/stack:200000000") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4") #define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout); #define all(x) x.begin(), x.end() #define sz(s) (int)s.size() #define pb push_back #define ppb pop_back #define mp make_pair #define s second #define f first using namespace std; typedef pair < long long, long long > pll; typedef pair < int, int > pii; typedef unsigned long long ull; typedef vector < pii > vpii; typedef vector < int > vi; typedef long double ldb; typedef long long ll; typedef double db; const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 333; const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9); const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 1e6 + 5e5 + 11; const db eps = 1e-12, pi = 3.14159265359; const ll INF = 1e18; int n, m, q, x[N], y[N], tp[N], a[N], b[N], z[N]; bool CHECK () { for (int i = 1; i <= q; ++i) if (tp[i] == 3) return 0; return 1; } map < int, int > t[N]; void upd1 (int x, int y, int z) { while (y <= inf) { t[x][y] = max(t[x][y], z); y |= y + 1; } } void upd (int x, int y, int z) { x = N - x; y = inf - y; while (x < N) { upd1(x, y, z); x |= x + 1; } } int get1 (int x, int y) { int res = 0; while (y >= 0) { if (t[x].count(y)) res = max(res, t[x][y]); y = (y & (y + 1)) - 1; } return res; } int get (int x, int y) { x = N - x; y = inf - y; int res = 0; while (x >= 0) { res = max(res, get1(x, y)); x = (x & (x + 1)) - 1; } return res; } main () { scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= m; ++i) scanf("%d%d", &x[i], &y[i]); for (int i = 1; i <= q; ++i) { scanf("%d%d", &tp[i], &a[i]); if (tp[i] == 4) scanf("%d", &b[i]); } if (m <= 2000 && q <= 5000) { for (int i = 1; i <= q; ++i) { if (tp[i] == 1) printf("%d %d\n", x[a[i]], y[a[i]]); else if (tp[i] == 3) { for (int j = 1; j <= m; ++j) if (x[j] <= a[i]) y[j] = max(y[j], n - a[i]); } else if (tp[i] == 2) { for (int j = 1; j <= m; ++j) if (y[j] <= a[i]) x[j] = max(x[j], n - a[i]); } else { x[++m] = a[i]; y[m] = b[i]; } } return 0; } if (CHECK()) { for (int i = 1; i <= q; ++i) if (tp[i] == 1) printf("%d %d\n", y[a[i]], max(x[a[i]], get(z[a[i]], y[a[i]]))); else if (tp[i] == 2) upd(i, a[i], n - a[i]); else { x[++m] = a[i]; y[m] = b[i]; z[m] = i; } return 0; } }

Compilation message (stderr)

sweeping.cpp:89:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
sweeping.cpp: In function 'int main()':
sweeping.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &m, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x[i], &y[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &tp[i], &a[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:96:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &b[i]);  
    ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...